On the LL1 list, it was claimed that strict functional languages make it impossible to cache computations without changing the interface. Alan Bowden replied with this bit of Haskell code that defines a memoized definition of fibonnaci numbers.
fib = ((map fib' [0 ..]) !!)
where
fib' 0 = 0
fib' 1 = 1
fib' n = fib (n - 1) + fib (n - 2)
This is a very interesting example of Haskell. It makes pleasant use of the mechanics of haskell in order to curry the !! operator so that it's invisible to the caller. But what I like most is that it manages to present a clean example of how to solve almost any dynamic programming problem in haskell, using only a few lines of code.
Unfortunately, while the code is very interesting, it doesn't really address the original problem of providing caching internal to the implementation of a function. In particular, it's not possible to extend this technique to allow cache eviction.
Posted on November 3, 2003 06:58 PM
More languages articles