[Haskell-cafe] Memoization/call-by-need

Ketil Malde ketil at malde.org
Thu Sep 16 04:14:01 EDT 2010

Alex Rozenshteyn <rpglover64 at gmail.com> writes:

> I understand that

>> fib50 = slowFib 50

> will take a while to run the first time but be instant each subsequent call;
> does this count as memoization?

I didn't see anybody else answering this in so many words, but I'd say
no, since you only name one particular value.  Memoization of slowFib
would mean to provide a replacement for the *function* that remembers
previous answers.

Try e.g. these in GHCi (import (i.e. :m +) Data.Array for memoFib):

  slowFib 0 = 1; slowFib 1 = 1; slowFib x = slowFib (x-1) + slowFib (x-2)
  memoFib x = a!x where a = listArray (0,n) (1:1:[ a!(x-1)+a!(x-2) | x<-[2..99]])

If I haven't seen further, it is by standing in the footprints of giants

More information about the Haskell-Cafe mailing list