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.