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