Llaisdy

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.