[<<][meta][>>][..]

Mon Feb 8 16:09:41 CET 2010

Haskell and memoization

See [1] section 2) Memoization with recursion.

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

The '!!' operator is array indexing, which appears curried here;
i.e. the last line is the same as:

   in  ((map fib [0 ..]) !!)

Which returns a function that maps an Int to one of the elements in
the list.

In general, using a memoized y-combinator it is possible to memoize
recursive functions by making sure they recurse into a memoized
version of themselves.

[1] http://www.haskell.org/haskellwiki/Memoization

[Reply][About]

[<<][meta][>>][..]