When looking up memoization in Haskell, I found this bit of code:
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'm trying to make sense of why this code memoizes, but I don't understand the use of !! in the second line. The only use I know of !! is as an operator to retrieve an element in a list by index, and I haven't been able to find anything else.
It might be clearer what’s going on if we add a few names and lift things out of the where clause.
memoized_fib :: Int -> Integer
memoized_fib i = fib_table !! i
fib_table :: [Integer]
fib_table = map fib [0 ..]
fib :: Int -> Integer
fib 0 = 0
fib 1 = 1
fib n = memoized_fib (n-2) + memoized_fib (n-1)
map fib [0 ..] makes a list [fib 0, fib 1, fib 2, …] that serves as our memoisation table. memoized_fib is a closure that contains a reference to this table. Given an index argument the closure uses !! to look up a result by index in the table, which will force that result to be computed — supposing you use it for something, like printing it out.
The important thing is that the table can be shared, because both fib_table and fib are independent of the choice of index i. So the helper definitions don’t need to be in a where clause, that’s just to keep memoized_fib self-contained — and in fact, to guarantee memoisation, i needs to be outside the scope of the helpers, so they can’t depend on i.
non_memoized_fib i = fib_table !! i
where
fib_table = map fib [0 ..]
-- =
non_memoized_fib =
\i -> let
fib_table = map fib [0 ..]
in fib_table !! i
memoized_fib = \i -> fib_table !! i
where
fib_table = map fib [0 ..]
-- =
memoized_fib = (fib_table !!)
where
fib_table = map fib [0 ..]
Since the table is a lazy list, it will be computed on demand. For a result that hasn’t been computed yet, fib will call memoized_fib so that it can reuse the saved results for any subcomputations that have already been done.
If fib just called itself directly, fib_table would still hold a memoised result for any specific index you computed, but each one would be computed separately: it wouldn’t share any of the work with lower indices.