Sorting an Array in PureScript

In general there are three ways of ordering an array in PureScript. In this article we will explore those three and point out the concepts behind each method and the Ord type class.

In general we will work with the three methots sort, sortBy and sortWith in the Data.Array module from the purescript-arrays package. But first, let's take a step back and examine the Ord type class:

class (Eq a) <= Ord a where

The Ord type class represents types which support comparisosn with a total order.

From the type class definition we know already that each member of the Ord type class needs to be as well a member of the Eq type class (which helps up to decide if two candidates are equal to each other.) Furthermore each member needs to provide a function compare:

compare :: a -> a -> Ordering

So we take two candidates of same type and get an Ordering as a result. But what is this Ordering? Let's have a look at the Data.Ordering from the prelude package:

The Ordering data type represents the three possible outcomes of comparing two values: LT - The first value is less than the second. GT - The first value is greater than the second. EQ - The first value is equal to the second.<br>

As always in PureScript, we are longing for type safety. We can have three predefined results LT, GT and EQ. EQ will be managed by our Eq condition. LT and GT needs to be implemented.

Ok, we know how sorting is supposed to work in PureScript, which type classes are used and what they imply. But how to we implement a member of Ord? Here is an example. Let's sort the following record by title:

data MyCustomRecord = { title :: String, publishDate :: DateTime }

instance ordMyCustomRecord :: Ord MyCustomRecord where
  compare candate1 candidate2 =
    if candidate1.title > candiate2.title then
      GT
    else if candidate1.title < candidate2.title then
      LS
    else
      EQ

This was we have added our data record to the Ord type class. Our implementation is telling us that we will sort an array of our records by the title of the record.

We can now go back to our three function sort, sortBy and sortWith.

sort in PureScript

The sort method will sort all members of an Array in increasing order. Hence, since Int is a member of Ord, the sample array [3,1,5] will become [1,3,5]. The function returns a new Array with the ordered items, following the principle of immutability. We can not do much about how we sort. To have an array sorted in decreasing order we would sort first and use reverse to have the correct result.

In our example of MyCustomRecord, if we use sort on an array of custom records we would get a new array with those records ordered in increasing order by its title.

sortBy in PureScript

So we now know how to use sort. We just need to add our custom record to the Ord type class. But writing the instance of a type class has its limitations. It is in a way some boilerplate code and we limit our self to a default sort function. There are cases where this can be a good decision (for instance on "native" types, like Number, Int, String, etc.) though. 

But let's imagine we have a front-end UI with a table of our custom records and the user can sort this table by title or by publishedDate (ascending or descending order). We are stuck with our instance implementation. Lukily we have sortBy. SortBy is the same but instead of taking a default implementation we can pass our function to sort. So let's create to functions for sorting (I will omit the implementation since it is the same / similar to the type class instance):

compareByTitle :: MyCustomRecord -> MyCustomRecord -> Ordering
compareByTitle candidate1 candidate2 = ...

compareByPublishDate :: MyCustomRecord -> MyCustomRecord -> Ordering
compareByPublishDate candidate1 candidate2 = ...

Now we can pass one of the functions to our sortBy function:

let sortedRecordsByTitle = sortBy compareByTitle customRecords
-- or
let sordedRecordsByPublishDate = sortBy compareByPublishDate customRecords

sortWith in PureScript

If you managed to read this far, you will ask yourself if there is another way of being flexible without writing similar code over and over again. This is where sortWith comes into play. It makes use of the Ord typeclass internally. What it needs is a hint on how to access "an orderable" value from our custom record. Since title is String - which is a member of Ord - and publishedDate is DateTime - which is a member of Ord as well - we can use both for sorting. This way we can sort our custom records without even providing an extra sort function:

let sortedRecordsByTitle = sortWith (\rec -> rec.title) customRecords
let sortedRecordsByPublishDate = sortWith (\rec -> rec.publishDate) customRecords