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

Ivan Uemlianin ivan at llaisdy.com
Mon Jun 22 06:03:02 EDT 2009

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]
        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.

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))

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?

Thanks and best wishes


Ivan A. Uemlianin
Speech Technology Research and Development

                    ivan at llaisdy.com

    "Froh, froh! Wie seine Sonnen, seine Sonnen fliegen"
                     (Schiller, Beethoven)

More information about the Beginners mailing list