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@tcs.inf.tu-dresden.de