Comparing multiple criteria
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
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-
> 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
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
> 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!
Monoids are cool. Read this for example:
Leave a comment!
Martijn loves to receive comments! Add yours by filling out the fields below.