[Haskell] Memo function help

MR K P SCHUPKE k.schupke at imperial.ac.uk
Wed Jul 28 05:03:36 EDT 2004


>Note that it doesn't have to be lazy, 

Most traditional dynamic programming techniques use arrays to store
intermediate values.

Lazy techniques could use a prohibative amount of memory due to the
size of the thunks.

The best general technique I have found in Haskell is to use 
unboxed mutable arrays in the ST monad to compute the result
eagerly. Even this can result in huge memory usage.

The best lazy technique I have seen is this:

http://www.csse.monash.edu.au/~lloyd/tildeStrings/Alignment/92.IPL.html

(in tests this lazy method was more or less the same speed as
the eager method, but it does take advantage of particular
access patterns in the string edit distance algorithm).

	Keean.


More information about the Haskell mailing list