# Comparing and Sorting in Elm

April 15, 2020 - Matt Furness

In this short post we will take a peek at how values can be compared and sorted in Elm, with the goal of sorting a `List`

of records using multiple criteria. It assumes you are familiar with Elm’s syntax, and is based on Elm version `0.19.1`

. It will also link to a smidgen of Haskell, however you do not need to know any Haskell to understand this post so feel free to ignore.

## The `comparable`

constrained type variable

There are a few constrained type variables in Elm, and `comparable`

is one of them. What this means (at the time of writing) is that a type variable named `comparable`

can only be “filled in” with `Int`

, `Float`

, `Char`

, `String`

, and lists/tuples of `comparable`

values. Constrained type variables are a little confusing when you first encounter them because there is nothing really to distinguish them from regular type variables, you just have to know that they exist. There has been a lot of discussion about this and there is a meta issue tracking type system extensions if you are interested in diving a bit deeper.

A common place to hit this limitation is with the built in `Set`

and `Dict`

types. Elements in a `Set`

must be `comparable`

and keys in a `Dict`

must be `comparable`

. The compiler gives some suggestions on how to deal with this, and there are some custom Elm packages that handle any type with their own pros and cons.

## Sorting lists

The List module has three sort functions:

`sort : List comparable -> List comparable`

If all of the elements of the list are one of the`comparable`

types mentioned above, you can use this very convenient function.`sortBy : (a -> comparable) -> List a -> List a`

If you can map all of the elements of a list to one of the`comparable`

types mentioned above you should use this function. This is particularly handy if you want to sort by a record field that is`comparable`

`sortWith : (a -> a -> Order) -> List a -> List a`

This is the most flexible, and gives you complete control over the ordering by taking a function that takes two list elements of any type and returns an`Order`

. This is the function that we will eventually make use of to sort a record using multiple criteria.

Order represents the relative ordering of two values, if you have ever encountered Ordering in Haskell, it serves the same purpose. I personally love the explicitness of this type compared to the use of Integer for this purpose in some traditional/mainstream languages. To get an `Order`

from two `comparable`

you can call the `Basics.compare`

function

*A quick note, for those interested, Order/Ordering is a Monoid and the Eq variant is identity. This comes in very handy when sorting by multiple fields as we will see later*

## Sorting a record by multiple fields

To sort a list of records by multiple fields we are going to start with a contrived record declaration:

```
import Date exposing (Date)
type alias Person =
{ name : String
, dateOfBirth : Date
}
```

The `Date`

type comes from the handy `justinmimbs/date`

module which also comes with the function:

`compare : Date -> Date -> Order`

Notice that it has the signature that matches the first argument to `List.sortWith`

. To install the package simply run `elm install justinmimbs/date`

.

We will also use another very handy package when it comes to comparing and sorting
`NoRedInk/elm-compare`

. To install it simply run `elm install NoRedInk/elm-compare`

. The first thing to know about the `Compare`

module is the `Comparator`

type alias:

```
type alias Comparator a =
a -> a -> Order
```

This type aliases the function that is the first argument to `List.sortWith`

, the rest of the module contains handy combinators for `Comparator`

.

Armed with these two extra modules let’s make a function that sorts a `List Person`

by date of birth (with the youngest first), if two dates are the same, then by their name alphabetically. The `name`

field is a `String`

which is a `comparable`

, but to work with the functions in the `Compare`

module we need a `Comparator`

. The `Compare.by`

function with the signature:

`by : (a -> comparable) -> Comparator a`

does just that:

```
import Compare exposing (Comparator)
nameComparator : Comparator Person
nameComparator =
Compare.by .name
```

Next we will create a `Comparator Person`

that will sort by dates (latest date first):

```
dateOfBirthComparator : Comparator Person
dateOfBirthComparator =
Compare.compose .dateOfBirth Date.compare |> Compare.reverse
```

This is where things get a little bit more interesting. The `Compare.compose`

function has a signature of:

`compose : (a -> b) -> Comparator b -> Comparator a`

That signature can look pretty weird if it is the first time you have seen something like it. You might think to yourself, *wait* if I give it a function from `a -> b`

how can we start with `Comparator b`

and end up with `Comparator a`

. The key to understanding it is to remember that a `Comparator`

is an alias of a function. It can help to substitute the type variables with the types we are working with:

`compose : (Person -> Date) -> Comparator Date -> Comparator Person`

Then to expand the `Comparator`

type alias to see the function types involved:

`compose : (Person -> Date) -> (Date -> Date -> Order) -> (Person -> Person -> Order)`

In other words if you give the compose function a way to go from a `Person`

to a `Date`

and a way to compare dates, then it returns a function that can compare people. To compare people it will first call the function that maps a `Person`

to a `Date`

(on each `Person`

) then compare those dates using the compare function provided.

*A quick aside, having done a wee bit of Haskell before learning Elm the name compose threw me a little. In Haskell the compose function is known as contramap or >$< which is a function on the Contravariant typeclass, and Contravariant does indeed have a Comparison instance. In other words, if you are familiar with Contravariant Functors you may have spotted that the Comparator type alias we have been using is indeed an example of one.*

By default the `Date.compare`

function sorts dates from earliest to latest, but we can use the `Compare.reverse`

, with the signature:

`reverse : Comparator a -> Comparator a`

This takes our `Comparator`

and reverses it. The nice thing about this function is that we don’t need to sort the `List`

only to reverse the `List`

, and crucially when sorting by multiple criteria we can reverse a specific `Comparator`

Now it is time to make a `Comparator`

that takes into account both of the previous ones.

```
personComparator : Comparator Person
personComparator =
Compare.concat [ dateOfBirthComparator, nameComparator ]
```

This uses `Compare.concat`

to make a `Comparator Person`

that compares people based on the `dateOfBirthComparator`

first and if that produces an `Order`

of `Eq`

it uses the `nameComparator`

, which is exactly what we want! In other words `Compare.concat`

will try each `Comparator`

in the list in order until it finds the first non-equal result, or it reaches the end of the list and it deems them equal.

*A quick note on Comparator as a Monoid, I will use the Haskell types so I can link to the docs. This is where Ordering being a Monoid and therefore Comparison being a Monoid comes in handy, mconcat on the Monoid instance for Comparsion works the same as the Compose.concat function, it is also why mempty (or identity) can be the Eq variant. There is a* shout out

*to this in the Monoid section of the Haskell Wiki*

All that is left to do now is to make the function that will sort a list of people:

```
sortPeople : List Person -> List Person
sortPeople =
List.sortWith personComparator
```

We just need to pass our `personComparator`

to `List.sortWith`

and we are done.

## Wrapping Up

Hopefully this has shed a bit of light on how to compare and sort in Elm. Armed with the `Compare`

module you can build up complex custom sorting for use with `List`

in an elegant and composable way.