[Haskell-cafe] Longest increasing subsequence

Ariel J. Birnbaum valgarv at gmx.net
Thu Apr 10 17:05:17 EDT 2008

The article mentioned in this thread addresses a similar problem:

The main idea is to start by expressing the straightforward, inefficient 
solution ,in this case something like:
  liss = maximumBy length . filter ascending . concat . map inits . tails
 (with ascending :: (Ord a) => [a] -> Bool defined appropriately)
Then apply a series of manipulations to it (each justified by a theorem)
in order to arrive at the functional version of your favorite algorithm =)

Some known names for (instances/applications of) this technique are map/fold 
fusion, deforestation and MapReduce. All the cool kids go bananas over it ;)

Ariel J. Birnbaum

More information about the Haskell-Cafe mailing list