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](https://guide.elm-lang.org/types/reading_types.html#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](https://github.com/elm/compiler/issues/1039) 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](https://github.com/elm/compiler/blob/master/hints/comparing-custom-types.md) on how to deal with this, and there are some custom [Elm packages](https://package.elm-lang.org/) that handle any type with their own pros and cons. ## Sorting lists The [List module](https://package.elm-lang.org/packages/elm/core/latest/List) has three [sort functions](https://package.elm-lang.org/packages/elm/core/latest/List#sort): - `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](https://package.elm-lang.org/packages/elm/core/latest/Basics#Order) represents the relative ordering of two values, if you have ever encountered [Ordering](https://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Ord.html#t: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](https://package.elm-lang.org/packages/elm/core/latest/Basics#compare) _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](https://package.elm-lang.org/packages/justinmimbs/date/latest) 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`](https://package.elm-lang.org/packages/NoRedInk/elm-compare/latest). 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](https://package.elm-lang.org/packages/NoRedInk/elm-compare/latest/Compare#by) 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 `>$<`](https://hackage.haskell.org/package/contravariant-1.4/docs/Data-Functor-Contravariant.html#v:contramap) which is a function on the `Contravariant` typeclass, and `Contravariant` does indeed have a [`Comparison` instance](https://hackage.haskell.org/package/contravariant-1.4/docs/Data-Functor-Contravariant.html#t:Comparison). 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`](https://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Functor-Contravariant.html#g:4) 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](https://wiki.haskell.org/Monoid#So_what.3F) _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.