Re: [Haskell-beginners] decorate-sort-undecorate in haskell

Am Dienstag 23 Juni 2009 15:42:59 schrieb Henk-Jan van Tuyl:

On Tue, 23 Jun 2009 14:58:11 +0200, Brandon S. Allbery KF8NH

wrote:

...

On Jun 22, 2009, at 06:03 , Ivan Uemlianin wrote:

...

I'm learning Haskell from a background in Python, and I'm just looking at the sort and sortBy functions in Data.List. In Python, the decorate-sort-undecorate pattern is a popular alternative to using an explicit compare function. For example, to sort a list of lists by

It's fairly common, considering that decorate-sort-undecorate is a functional programming idiom dating back to Lisp. In Haskell it's usually expressed with the decoration in a tuple such that the default sort can be used.

...

map snd . sort . map (\x -> (x,decorate x))

Typo: map snd . sort . map (\x -> (decorate x,x))

...

Fancier versions use arrows to make the decorate part cleaner:

...

map snd . sort . map (decorate &&& id)

The simplest form for e.g. sorting by length is:

...

sortByLength = sortBy (comparing length)

But that is an example where the decoration really shines, except all lists are very short: Prelude> :set +s Prelude> let lens :: [Int]; lens = [(k^2+3*k-2) `mod` 5431 | k <- [1 .. 500]] (0.04 secs, 6184112 bytes) Prelude> let lists = map (flip replicate ()) lens (0.00 secs, 609084 bytes) Prelude> :m +Data.List Prelude Data.List> :m +Data.Ord Prelude Data.List Data.Ord> let srtl1 = sortBy (comparing length) lists (0.00 secs, 0 bytes) Prelude Data.List Data.Ord> let srtl2 = map snd . sortBy (comparing fst) $ map (\l -> (length l, l)) lists (0.02 secs, 5975640 bytes) Prelude Data.List Data.Ord> length (srtl2 !! 420) 4471 (0.19 secs, 37089168 bytes) Prelude Data.List Data.Ord> length (srtl1 !! 420) 4471 (1.09 secs, 542788 bytes) simpler is not always better.