[<<][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][>>][..]