[Haskell] Memo function help
GK at ninebynine.org
Tue Jul 27 15:27:00 EDT 2004
At 16:24 27/07/04 +0000, Tom Hofte wrote:
>I want to use the memo function for implementing a dynamic programming
>algorithm in Haskell.
>This is needed to cache intermediate results.
>Can anyone tell me where I can find some examples that use the memo
>function or even a tutorial.
As I understand it, this is not so much a "memo function" as a programming
technique called "memoization".
I've not seen this explained clearly in any single place, but my
understanding is this:
- rather than using a function to perform a calculation, use some kind of
indexed data structure to hold the results, initialized with appropriate
- lazy evaluation means actual calculation of any value in the structure is
suspended until it is actually needed, at which point the suspended
calculation is replaced by the resulting value.
- subsequent accesses to a previously calculated value simply return that
value, hence the cache-effect.
I'm expecting that others will correct me if I got that wrong, but I think
that's about how memoization can be used.
Googling for "Haskell memoization" returns a couple of examples (Fibonacci
calculation is a popular one); I didn't see a clear tutorial there, but I
didn't look beyond the first few hits.
More information about the Haskell