Orderer

(This is an exercise in literate programming for me.)

> import Data.List(sortBy)
> import Data.Ord(comparing)

Let’s say we have a list of fruits:

> data Fruit = Fruit { color :: String, name :: String } deriving (Show, Eq)
>
> fruits = [
>     Fruit "Yellow" "Banana",
>     Fruit "Red"    "Tomato",
>     Fruit "Green"  "Kiwifruit",
>     Fruit "Red"    "Strawberry",
>     Fruit "Yellow" "Lemon",
>     Fruit "Green"  "Cucumber"
>   ]

We want to sort them by color. That’s easy:

> order1 = sortBy (comparing color)

But what if we want to sort them first by color and then by name? Like ORDER BY color, name in SQL?

Well, let’s begin by introducing orderers:

> type Orderer a = a -> a -> Ordering

An orderer is something that takes two of something and returns their ordering. comparing turns any function Ord b => (a -> b) to an Orderer b.

If we want to sort by two criterias, we basically just want to combine two orderers. Here’s a simple combinator for that:

> andThenBy :: Orderer a -> Orderer a -> Orderer a
> andThenBy f g x y = let a = f x y; b = g x y
>                     in if a == EQ then b else a

It can be used like this:

> order2 = sortBy (comparing color `andThenBy` comparing name)

Note how nice that reads out: Sort by comparing color and then by [comparing] name.

If we have many criteria we can use a helper function to combine a list of orderers into one:

> comparingMany :: [Orderer a] -> Orderer a
> comparingMany = foldl andThenBy (\ x y -> EQ)
>
> order3 = sortBy (comparingMany [comparing color, comparing name])

Now we can get even closer to ORDER BY color, name by introducing another function:

> orderBy = sortBy . comparingMany
>
> order4 = orderBy [comparing color, comparing name]

Pretty succinct!

And now, a little advertisement: This page was generated with textile+lhs2html!