[Haskell] Memo function help

[Graham Klyne]

At 16:24 27/07/04 +0000, Tom Hofte wrote:
>Hi,
>
>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 
expressions
- 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.

#g


------------
Graham Klyne
For email:
http://www.ninebynine.org/#Contact