Haskell: Why does this work -- an example of memoization?

Question

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?

The memoization breaks the way you are thinking of if you change the definition to `memoized_fib n = map fib [0 ..] !! n`. I don't know shy but maybe someone else can shed some light on it. — hugomg, Jan 05 '14 at 16:03
http://blog.ezyang.com/2011/04/the-haskell-heap/ is a great series about the haskell heap, it might also explain this (not sure), but even if not it's a good read! — bennofs, Jan 05 '14 at 16:24

n. m. could be an AI · Accepted Answer · 2014-01-05T16:22:02.313

12

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).

edited Jan 05 '14 at 16:22

answered Jan 05 '14 at 16:16

n. m. could be an AI

112,515
14
128
243

So does it mean that there will be only one ```memized_fib``` instance ? How do I tell whether a function is a CAF or not? Thanks :) – Bob Fang Jan 05 '14 at 16:30
1

Yes, only one. You check it against the definition in the linked article ;) – n. m. could be an AI Jan 05 '14 at 16:50
1

Thanks first, and I mean no offence but the problem here is that after I click into the link I found that I do not know anything about Super combinator and after clicking into it I found I do not know what is a Combinator, and then it is defined as "A function with no free variables", free variables? never heard of it. Probably I missed the most important thing before learning Haskell, i.e. learn lambda calculus and category theory first! – Bob Fang Jan 05 '14 at 17:05
Yes, a bit of lambda calculus and category theory won't hurt! – n. m. could be an AI Jan 05 '14 at 17:25
3

@dorafmon: Lambda calculus definitely. It’s the core of modern functional languages. Category theory on the other hand is only necessary if you want to write or understand the internals of libraries that take advantage of results from category theory. – Jon Purdy Jan 05 '14 at 19:35

score 8 · Answer 2 · answered Jan 05 '14 at 20:18

I can explain missingno's observation, and it may help you understand the behaviour you are seeing. It's important to understand what the where clause desugars to.

The code you presented is

memoized_fib = (map fib [0 ..] !!)
    where fib = ...

which desugars to

memoized_fib = let fib = ...
               in \n -> map fib [0 ..] !! n

missingno presented the following, which looks like a simple eta expansion, but it's not!

memoized_fib n = map fib [0 ..] !! n
    where fib = ...

desugars to

memoized_fib = \n -> let fib = ...
                     in map fib [0 ..] !! n

In the former case you can see that the fib structure is shared between invocations of memoized_fib whereas in the latter casefib is reconstructed each time.

In the first case where you say that `fib` is shared. Why is it shared? Are you saying `memoized_fib = let fib = ...` doesn't redeclare the `fib` when it's called again? It reuses the prior `fib`? Does that mean it's equivalent to having the `fib` defined outside the `memoized_fib` function? — CMCDragonkai, Jul 31 '15 at 07:47
Yes, it's equivalent to defining `fib` outside `memoized_fib`. — Tom Ellis, Aug 01 '15 at 06:30

score 1 · Answer 3 · edited May 23 '17 at 11:58

The code that you show depends on a given compiler's behaviour. Here's the desugaring like Tom Ellis suggested:

memoized_fib = 
    let   fib 0 = 0
          fib 1 = 1
          fib n = memoized_fib (n-2) + memoized_fib (n-1)
    in
       (map fib [0 ..] !!)

Nothing guarantees that the list map fib [0..] will be reused, i.e. "shared". Especially when you omit the type signature, like I did, making this a polymorphic definition.

Better make that list explicit, giving it a name:

memoized_fib n = 
    let   fib 0 = 0
          fib 1 = 1
          fib n = g (n-2) + g (n-1)
          g = (fibs !!)
          fibs = map fib [0 ..]
    in
       g n

This was discussed before.

Haskell: Why does this work -- an example of memoization?

3 Answers3