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

wren ng thornton wren at freegeek.org
Thu Sep 16 00:10:43 EDT 2010

On 9/15/10 10:39 PM, Conal Elliott wrote:
> Hi Alex,
> In Haskell, data structures cache, while functions do not.

Exactly. What this means is that when you call (slowFib 50) Haskell does 
not alter slowFib in any way to track that it maps 50 to $whatever; 
however, it does track that that particular expression instance 
evaluates to $whatever. This is why, when you define fib50=(slowFib 50) 
it only needs to compute $whatever the first time the value of fib50 is 
required. After the first evaluation it's the same as if we had defined 

So, the function being memoized is the evaluation function of Haskell 
itself, not any of the functions _in_ the language. There are various 
libraries for memoizing functions in Haskell, they're just not part of 
the language definition.

Live well,

More information about the Haskell-Cafe mailing list