Haskell: sort and sortBy

Friday, 3rd July, 2009

A comment in the discussion on decorate-sort-undecorate in Haskell pointed out to me that my naive and dsu versions of sort by length had different type signatures: the dsu version needlessly required elements of the list to be of type Ord:

sortByLength :: [[a]] -> [[a]]
sortByLength xs = sortBy (comparing length) xs

dsuSortByLength1 :: (Ord a) => [[a]] -> [[a]] 
dsuSortByLength1 xs = map snd (sort (zip (map length xs) xs))

My intention had been that the dsu version have the same requirements as the naive version. So where did this (Ord a) context come from, and how do we get rid of it?

The relevant difference between the functions is the different type signatures for sort and sortBy:

> :type sort
sort :: (Ord a) => [a] -> [a]
> :type sortBy
sortBy :: (a -> a -> Ordering) -> [a] -> [a]

sort requires list elements to be comparable (obviously); sortBy requires only a function that can generate an ordering from its input pair. In dsuSortByLength1 above, the elements of (zip (map length a) a) are required to be of type Ord. We could protest that just because (zip (map length a) a) has to be Ord doesn’t mean that a has to be Ord, but I suspect the compiler is playing on the safe side. [update: see first two comments.]

A function using sortBy instead of sort avoids this extra requirement in the type signature, and shows us a use case for comparing:

sortByLength :: [[a]] -> [[a]]
sortByLength xs = sortBy (comparing length) xs

dsuSortByLength2 :: [[a]] -> [[a]] 
dsuSortByLength2 xs = map snd (sortBy (comparing fst) (zip (map length xs) xs))

Using sortBy (comparing fst) rather than sort allows us to simplfy the type signature.

We can extract length to generalise the function:

sortByFunc :: (Ord a) => (a1 -> a) -> [a1] -> [a1]
sortByFunc f xs = sortBy (comparing f) xs

dsuByFunc  :: (Ord a) => (a1 -> a) -> [a1] -> [a1]
dsuByFunc  f xs = map snd (sortBy (comparing fst) (zip (map f xs) xs))

The (Ord a) context has returned! But here it is just a requirement on the output of the comparison function, which is fine.

4 Responses to “Haskell: sort and sortBy”

  1. Jeff Says:

    The compiler wasn’t just being safe; there is a difference between the two. dsuSortByLength is comparing tuples of (length x,x); so when two elements have the same length, it will then sort them lexicographically. sortByLength, on the other hand, leaves equal-length elements in their original order, since sort/sortBy is stable.

    That is:

    > sortByLength [“bb”, “b”, “a”, “c”, “aa”,”cc”]

    > dsuSortByLength [“bb”, “b”, “a”, “c”, “aa”,”cc”]
    [“a”,”b”,”c”,”aa”,”bb”, “cc”]

  2. llaisdy Says:

    Jeff, thanks for your comment, that’s perfect. I’ve just tried dsuSortByLength2 and it works just like sortByLength.

    dsuSortByLength1 is comparing (length x, x), so x has to be Ord as it’s part of the comparison; sortByLength a dn dsuSortByLength2 are comparing just length x, so there’s no requirement on x itself.

    I get it now, thanks again.

  3. Nicolas Pouillard Says:

    You can also write dsuByFunc in a more point-free style:

    dsuByFunc f = map fst . sortBy (comparing snd) . (zip `ap` map f)

  4. llaisdy Says:

    Nicolas, thanks for your comment.

    Very timely: ‘.’ (and ‘$’ and ‘&&&’ and maybe others) will be the subject of my next post!

    ap appears to be monadic so I’ll be leaving that until I come to monads.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: