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

[Daniel Fischer]

Am Montag 22 Juni 2009 12:03:02 schrieb Ivan Uemlianin:
> Dear All
>
> 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 length:
>
>     def sortByLength(xs):
>         dec_xs = [(len(x), x) for x in xs]
>         dec_xs.sort()
>         undec_xs = [x[1] for x in dec_xs]
>         return undec_xs
>
> This is often preferred to something like:
>
>     xs.sort(lambda x,y: len(x) > len(y))  # just used lambda so it fits
> on one line
>
> I think the reasoning is that plain sort() is done at C speed, whereas
> sort(func) is done in Python, so, depending on the list I suppose, dsu
> can be worth the trouble.  (Sorry for vagueness).
>
> Anyway, I was wondering if dsu is popular in Haskell, and whether or
> when it would make sense to use dsu rather than sortBy.

It's moderately popular.
It makes much sense to use it, if the decoration function is expensive.

From http://www.haskell.org/haskellwiki/Blow_your_mind :

map snd . sortBy (comparing fst) . map (length &&& id) 
-- the so called "Schwartzian Transform" for computationally more expensive 
-- functions.

it even has a name :)
If you used

sortBy (comparing f)

f x would be recalculated each time you compare x, it's only calculated once with the 
Schwartzian transform

>
> Here's a verbose dsu I wrote myself:
>
>     sortDSU decFunc a =  undecorate (sort (decorate decFunc a))
>
>     decorate decFunc [] = []
>     decorate decFunc (x:xs) = ( ((decFunc x), x) : decorate decFunc xs )
>
>     undecorate [] = []
>     undecorate ( (_, y) :xs) = ( y : undecorate xs )
>
> Here's a terser and perhaps more idiomatic (but I think equivalent) dsu
> which I then found in a comment at the Real World Haskell website:
>
>     dsuSort decFunc a = map snd (sort (zip (map decFunc a) a))

more general:

dsuSort decFun a = map snd . sortBy (comparing fst) $ zip (mp decFun a) a

>
> I have tested both functions with length and sum in ghci.
>
> So, do Haskell programmers use the decorate-sort-undecorate pattern?  If
> not, why not? If so, when?

Sometimes. It's used if the decorating function is expensive, not if constructing and 
deconstructing tuples costs more than recalculating it (consider sortBy (comparing snd) as 
an extreme case).

>
> Thanks and best wishes
>
> Ivan