|

Comparing multiple criteria

Posted on Sunday, 21 December 2008 at 13:15.

import Data.List
import Data.Ord
import Data.Monoid

If in Haskell we want to sort a list of tuples on their first elements, we write:

tups :: [(Int, Int)]
tups = [(1,2),(1,0),(4,5),(3,9),(3,2)]

> sortBy (comparing fst) tups
[(1,2),(1,0),(3,9),(3,2),(4,5)]

Let’s assume there is no good default compare function for tuples. Now what if we wanted to compare on the second element if comparing on the first element wouldn’t discriminate two values? We could write a helper function:

compareTuple :: (Ord a, Ord b) => (a, b) -> (a, b) -> Ordering
compareTuple (x1, y1) (x2, y2) =
  case compare x1 x2 of
    EQ -> compare y1 y2
    ne -> ne

So that we can write:

> sortBy compareTuple tups
[(1,0),(1,2),(3,2),(3,9),(4,5)]

If we had to compare values on even more criteria, the nesting of case expressions would be even deeper. I want to make this easier to write.

In practice we usually have a list of criteria to compare on when sorting values. In the example above, these criteria are the first and second elements of the tuples, respectively. Let’s try and put these criteria in a list:

impossibleTupleCriteria :: [(a, b) -> ??]
impossibleTupleCriteria = [fst, snd]

But this is not valid Haskell, because fst and snd have different and ununifiable types and therefore cannot be in a list together. We can work around this by wrapping the criteria in a data constructor with an existentially qualified type variable, but since all we’re gonna do is call comparing on those functions anyway we might as well do that right away:

tupleCriteria :: (Ord a, Ord b) => [(a, b) -> (a, b) -> Ordering]
tupleCriteria = [comparing fst, comparing snd]

Now all that is left to do is fold this list of criteria into one criterion. It turns out there is a very easy way to do that in Haskell:

comparingMany :: [a -> a -> Ordering] -> a -> a -> Ordering
comparingMany = mconcat

> sortBy (comparingMany tupleCriteria) [(1,2),(3,9),(1,0),(4,5),(3,2)]
[(1,0),(1,2),(3,2),(3,9),(4,5)]

What’s going on here? mconcat is a function from the Monoid type class and works on multiple levels here. Firstly, the Monoid instance for Ordering does exactly what we want here, namely pick the first non-EQ value:

> mconcat [EQ, EQ, LT, GT]
LT
> mconcat [GT, EQ, GT]
GT
> mconcat [EQ, EQ]
EQ
> mconcat [] :: Ordering
EQ

Secondly, the monoid operations are ‘automatically’ lifted to functions:

instance (Monoid b) => Monoid (a -> b) -- Defined in Data.Monoid

Which happens twice in comparingMany.

What we have found now means we don’t need any helper functions anymore! Our new tuple comparing function now looks like:

compareTuple' :: (Ord a, Ord b) => (a, b) -> (a, b) -> Ordering
compareTuple' = mconcat [comparing fst, comparing snd]

Finally, if we want to reverse the natural ordering of a criterion (or of the whole set), simply use flip:

> sortBy (mconcat [comparing fst, flip $ comparing snd]) tups
[(1,2),(1,0),(3,9),(3,2),(4,5)]
> sortBy (flip $ mconcat [comparing fst, comparing snd]) tups
[(4,5),(3,9),(3,2),(1,2),(1,0)]

Thanks to vixey on #haskell for the hint to look at monoids!

Comments

By Sjoerd Visscher on Sunday, 21 December 2008 at 16:05:

Monoids are cool. Read this for example:
http://sigfpe.blogspot.com/2008/11/from-monoids-to-monads.html

Leave a comment!

Martijn loves to receive comments! Add yours by filling out the fields below.