[Haskell-cafe] Longest increasing subsequence

[Ariel J. Birnbaum]

The article mentioned in this thread addresses a similar problem:
http://lambda-the-ultimate.org/classic/message8282.html

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