Re: [Haskell-cafe] Longest increasing subsequence

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