[Haskell] Memo function help

Ketil Malde ketil+haskell at ii.uib.no
Wed Jul 28 01:16:04 EDT 2004

Graham Klyne <GK at ninebynine.org> writes:

>> I want to use the memo function for  implementing a dynamic
>> programming algorithm in Haskell.

> - 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.

I'm not sure about the theoretically correct definition of dynamic
programming, but I think you're onto it.  Note that it doesn't have to
be lazy, you can calculate the values for the complete space if you
want.  Very useful for any kind of recursive function that calls
itself more than once, but with decreasing argument values.  Typical
for graph or graph-like algorithms (HMM probabilities, sequence

If I haven't seen further, it is by standing in the footprints of giants

More information about the Haskell mailing list