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