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

[Daniel Fischer]

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
>
> <allbery at ece.cmu.edu> 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.