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.
I'm not sure if this will address your core confusion, but it's an answer I've had brewing for this code snippet for a while and have never had an excuse to write up. So here goes, I hope you'll enjoy it.
I'd like to convince you that you could have come up with this implementation yourself, just by starting with a bad piece of code and incrementally improving it in the most obvious ways possible, one step at a time. It starts like this:
fib :: Int -> Integer fib 0 = 1 fib 1 = 1 fib n = fib (n-1) + fib (n-2) You just read the Wikipedia definition of the sequence and wrote it down. And it works! It's just slow. You find that even for modest values of n, it takes an incredibly long time, and your Fibonacci-as-a-Service business consultants are starting to complain. So you come up with a clever plan: let's store a lookup table for answers. If we construct the lookup table lazily, then we won't have to pay the cost until the first time we need an answer, and after the first time it will be very fast because we'll look up the answer we already computed rather than recomputing it. If there's popular inputs that people request a lot, we'll pay the high computation cost the first time, but save a lot on the followup requests. So you write down the lazy table:
fibTable :: [Integer] fibTable = map fib [0..] Now to recover the original function, we can just do lookups in this table.
fibTableLookup :: Int -> Integer fibTableLookup n = fibTable !! n You deploy, and save tons of time, because it turns out everybody just wants to know the 100th Fibonacci number. The business analysts are thrilled. You boast about it to one of your coworkers in the coffee room a week later and they say, "Hm, cool! Can you use the table while you're doing the computation in the first place?". After a bit of thinking and confusing yourself, you decide to just try it and see what happens. Maybe it'll loop infinitely, that would be fun! So you open your module and change up the definition of fib:
fib :: Int -> Integer fib 0 = 1 fib 1 = 1 -- used to be: fib n = fib (n-1) + fib (n-2) fib n = fibTableLookup (n-1) + fibTableLookup (n-2) You are delighted when a bit of benchmarking shows that with the old definition, fibTableLookup 45 takes >10s on its first invocation, while with the new definition, fibTableLookup 45 is so fast your timer reports 0ms. You find you have to bump the input all the way to 2000 before it rolls over from 0ms to 1ms.
But, being a professional software engineer, there's one issue that bugs you: your module has some extra definitions lying around that are really just implementation details. You'd like to hide them away inside a where clause so there's just one visible, top-level definition. After a bit of thought, you decide because fibTable and fibTableLookup each have only one defining clause, it will be easier to refactor to keep one of those as the top level. You feel that fibTableLookup is the right level of abstraction, so you keep it and move everything into a where.
fibTableLookup :: Int -> Integer fibTableLookup n = fibTable !! n where fibTable = map fib [0..] fib 0 = 1 fib 1 = 1 fib n = fibTableLookup (n-1) + fibTableLookup (n-2) The fibTable definition looks short enough that you could inline it:
fibTableLookup :: Int -> Integer fibTableLookup n = map fib [0..] !! n where fib 0 = 1 fib 1 = 1 fib n = fibTableLookup (n-1) + fibTableLookup (n-2) You know one of your coworkers has been on a point-free kick recently. You decide to try a point-free version on for size and see if you like it, so you delete n from the first line:
fibTableLookup = (map fib [0..] !!) where This is the code you originally posted (with minor name changes). After staring at it a bit... Nah. Too confusing. You revert to the pointed version and say a silent "You're welcome!" to the next person who has to dig in and read this code.
Your Haskell-expert coworker does warn you about one thing with the pointed version, though: it relies heavily on the GHC optimizer. Without optimizations, each time you call fibTableLookup, it creates a completely fresh lookup table, not shared with the other calls. You're now faced with a tricky decision, and the outcome turns out to depend on a quantum coin flip in your brain. In about half the continuations of the universe a neuron does fire and you decide to deal with this problem if it comes up rather than making the code harder to read now for a hypothetical problem that might never happen; in the other half, the neuron doesn't fire and you decide to make it robust now while you're thinking of it to avoid having to do an expensive debugging process later. Your coworker explains that if we bring back fibTable, we can use a trick to keep it pointed while making it robust to compiler flags:
fibTableLookup = \n -> fibTable !! n where fibTable = map fib [0..] 
The only use I know of !! is as an operator to retrieve an element in a list by index- and that's exactly what it is here. It might be easier to mentally parse in "non-point-free" form:memoized_fib n = map fib [0 ..] !! n.nargument allocates a different lookup table for every choice ofn, whereas the pointfree version allocates a single lookup table and shares it. Basically\n -> let table = ... in ...is different fromlet table = ... in \n -> ....-fno-full-laziness.