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

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

-- 
============================================================
Ivan A. Uemlianin
Speech Technology Research and Development

                    ivan at llaisdy.com
                     www.llaisdy.com
                         llaisdy.wordpress.com
                     www.linkedin.com/in/ivanuemlianin

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



More information about the Beginners mailing list