[Haskell-cafe] Longest increasing subsequence
robdockins at fastmail.fm
Thu Apr 10 17:17:15 EDT 2008
On Thursday 10 April 2008 01:20:49 pm Matt Amos wrote:
> 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.
Memorization is a nice way to implement dynamic programming algorithms in
Haskell. Basically, you arrange it so that the underlying runtime does the
destructive updates for you.
More information about the Haskell-Cafe