Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

composing two comparison functions?

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
like image 890
ErikR Avatar asked Jul 14 '12 18:07

ErikR


People also ask

How do you write a compare function for sorting?

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.


2 Answers

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

like image 150
jberryman Avatar answered Oct 22 '22 13:10

jberryman


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 two Ordering values, the one on the left is kept, unless the value on the left is EQ, in which case the right one is the result. The identity is EQ.

like image 42
Alessandro Pezzato Avatar answered Oct 22 '22 15:10

Alessandro Pezzato