Comparing and Sorting in Elm

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.