I'd like to sort by one property and then by another (if the first property is the same.)
What's the idiomatic way in Haskell of composing two comparison functions, i.e. a function used with sortBy
?
Given
f :: Ord a => a -> a -> Ordering
g :: Ord a => a -> a -> Ordering
composing f
and g
would yield:
h x y = case v of
EQ -> g x y
otherwise -> v
where v = f x y
The easiest way to write a sort comparison function is to generate the sort keys, and then compare the keys. For a multi-level sort, you can return a std::pair or std::tuple with the most significant key as the first element. Another is to use std::forward_as_tuple to make everything a reference.
vitus points out the very cool instance of Monoid
for Ordering
. If you combine it with the instance instance Monoid b => Monoid (a -> b)
it turns out your composition function is just (get ready):
mappend
Check it out:
Prelude Data.Monoid> let f a b = EQ
Prelude Data.Monoid> let g a b = LT
Prelude Data.Monoid> :t f `mappend` g
f `mappend` g :: t -> t1 -> Ordering
Prelude Data.Monoid> (f `mappend` g) undefined undefined
LT
Prelude Data.Monoid> let f a b = GT
Prelude Data.Monoid> (f `mappend` g) undefined undefined
GT
+1 for powerful and simple abstractions
You can use the <>
operator. In this example bigSort
sorts string by their numerical value, first comparing length and then comparing lexicographically.
import Data.List (sortBy)
import Data.Ord (compare, comparing)
bigSort :: [String] -> [String]
bigSort = sortBy $ (comparing length) <> compare
Example:
bigSort ["31415926535897932384626433832795","1","3","10","3","5"] =
["1","3","3","5","10","31415926535897932384626433832795"]
<>
is an alias of mappend
from the Data.Monoid module
(see jberryman answer).
The (free) book Learn You a Haskell for Great Good! explains how it works here in Chapter 11
instance Monoid Ordering where mempty = EQ LT `mappend` _ = LT EQ `mappend` y = y GT `mappend` _ = GT
The instance is set up like this: when we
mappend
twoOrdering
values, the one on the left is kept, unless the value on the left isEQ
, in which case the right one is the result. The identity isEQ
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With