Menu
Hi I am looking at this example from Memoization:
memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
where fib 0 = 0
fib 1 = 1
fib n = memoized_fib (n-2) + memoized_fib (n-1)
I am just wondering why this even work, since for me if you call memoized_fib(n-2) then you are "creating" a new list and doing things with it and after your return from it the list containing partial result would be gone? So memorized_fib(n-1) won't benefit from it at all?
922
Fortunately, it is possible to memoize a function without side effects thanks to Haskell's nature of lazy evaluation. The following memoize function takes a function of type Int -> a and returns a memoized version of the same function.
In programming, memoization is an optimization technique that makes applications more efficient and hence faster. It does this by storing computation results in cache, and retrieving that same information from the cache the next time it's needed instead of computing it again.
It helps avoid waste by removing the need to recalculate values that have already been produced as part of a previous call. The benefits of memoization will be less apparent in functions that are simple to begin with or infrequently called.
In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
memoized_fib is a CAF, which is as good as a literal constant in avoiding creation of new stuff. No variables ⇒ no things to bind new stuff to ⇒ no creation of new stuff (in simplified terms).
52
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
