[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