[Haskell-cafe] Longest increasing subsequence
matt at asklater.com
Thu Apr 10 13:20:49 EDT 2008
I'm trying to break out of my imperative mind-set by learning Haskell
in small snippets. After a few successes I've hit a bit of a
roadblock with one of the classic dynamic programming problems, the
longest increasing subsequence:
The most efficient algorithm relies on destructive updates, so a
simple translation doesn't seem possible. I've been trying to think of
a way of removing the need for destructive updates while keeping the
efficiency, but so far without much luck. Ideally, I'd like to avoid
threading the whole thing with a state monad, since then it would
just be an imperative algorithm in disguise.
Any suggestions would be very gratefully appreciated.
More information about the Haskell-Cafe