[Haskell-cafe] Memoizing longest-common-subsequence

[Janis Voigtlaender]

Mark T.B. Carroll wrote:
> Take this as your cue to point out the much better LCS algorithm that
> already exists in the standard libraries, that I couldn't find. (-:

I don't know of a version in the libraries, but since you mentioned you
were unsuccessful looking for any functional algorithms solving this
problem: I would be very surprised if none could be found in some paper
of Richard Bird's.

Also, something like the memoizing implementation you give should be
easily in reach using Giegerich and Kurtz' "algebraic dynamic
programming" approach that I recently mentioned here. Of course, it
would then be less straightforward to apply subsequent optimizations
(like strictifying and unboxing), as the details of the implementation
would be hidden inside their DSL.

Ciao, Janis.

-- 
Dr. Janis Voigtlaender
http://wwwtcs.inf.tu-dresden.de/~voigt/
mailto:voigt at tcs.inf.tu-dresden.de