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