Custom sorting functions and algorithms in F#

Sorting lists, arrays and sequences in F# is simple as long as you're not doing anything fancy. Using Seq.sort to sort a list of integers is trivial, and using Seq.sortBy to sort a list of records by an arbitrary property or field is similarly easy. But what happens when you need to do something a little more complicated?

For instance, what if you have a list of strings that need to be sorted alphabetically, except for the string "foo" which should always be sorted to the top of the list? Or what if you have a list of records that need to be sorted by one field, and then further sort any duplicates by another field? Those are the questions this article aims to answer.

Custom sorting a list of strings

At the core of most custom sorting algorithms in F# are three functions:

• Seq.sortWith
• Array.sortWith
• List.sortWith

These three functions are all identical in function, and which one you use just depends on what kind of list you're operating on (i.e. a generic enumerable sequence, an array, or an F# list). Here's what the documentation for Seq.sortWith says:

Seq.sortWith: (comparer: 't -> 't -> int) -> (source: 't seq) -> (output: 't seq)

Yields a sequence ordered using the given comparison function.

This function returns a sequence that digests the whole initial sequence as soon as that sequence is iterated. As a result this function should not be used with large or infinite sequences. The function makes no assumption on the ordering of the original sequence and uses a stable sort, that is the original order of equal elements is preserved. 

Breaking this down, it takes a comparison function that passes in two elements from the source enumerable and the comparison function must return an integer based on the result of that comparison. They don't really explain what that means though, so to make it much clearer than Microsoft's documentation: if the comparison returns a negative integer, the first element will be shifted left in the list compared to the right element; if it returns a positive integer, the first element will be shifted right in the list.

Here's an example of that comparison that's about as simple as possible. We'll pass in a list of two strings that we want to sort, and if we get the string "foo" we want to send it to the top of the list by returning a negative number if it's the first element or a positive number if it's the second:

let strings = [
    "bar"
    "foo"
]

let sort (a: string) (b: string) =
    if a = "foo" then
        -1
    else
        1

Seq.sortWith sort strings
|> Seq.iter (printfn "%s")

// Prints:
// foo
// bar

From this you can see the foundation of implementing custom sorting algorithms in F#. However, this simple example would fail if we wanted to implement the more complicated example of our alphabetical string sorting that also sorts the string "foo" to the top of the list. Introducing more strings to the list does not magically sort them in alphabetical order:

let strings = [
    "bar"
    "foo"
    "baz"
    "bat"
    "world"
    "hello"
]

let sort (a: string) (b: string) =
    if a = "foo" then
        -1
    else
        1

Seq.sortWith sort strings
|> Seq.iter (printfn "%s")

// Prints:
// foo
// bar
// baz
// bat
// world
// hello

You can see in this case, "foo" is still at the top of the list, but all of the other strings have remained in the same position and are not being sorted alphabetically.

So does that mean we need to implement our own alphabetical sorting algorithm, on top of the "foo" sorting algorithm, if we want implement the rest of our sorting requirement? Thankfully not, as this is where we can take advantage of F#'s built-in compare function to handle the more "simple" alphabetical sorting for us.

The compare function takes two comparable values and returns an integer based on the difference between those values. If you give it two strings, it will return a negative number if the first string comes before the second string alphabetically, and a positive number if the first string comes after the second string.

That's exactly the kind of result the Seq.sortWith function is looking for when sorting, which means you could literally pass in the compare function to have it alphabetically sort a list of strings. This will give you the exact same output as using the default Seq.sort function, which is using this string comparison under the hood:

let strings = [
    "bar"
    "foo"
    "baz"
    "bat"
    "world"
    "hello"
]

Seq.sortWith compare strings
|> Seq.iter (printfn "%s")

// Prints:
// bar
// bat
// baz
// foo
// hello
// world

// Identical to the default sorting from Seq.sort
Seq.sort strings
|> Seq.iter (printfn "%s")

// Prints:
// bar
// bat
// baz
// foo
// hello
// world

At this point we've seen how to sort "foo" to the top of a list, and we've seen how to sort any other string alphabetically. Now we can tie it all together in our custom "foo" sorting function. We just need the function to look at both the strings it's given to determine if either one of them is "foo" and return the correct sorting direction if so; if neither of them are "foo", though, it should return the result of compare to sort the strings alphabetically instead:

let strings = [
    "bar"
    "foo"
    "baz"
    "bat"
    "world"
    "hello"
]

let sort (a: string) (b: string) =
    if a = "foo" then
        -1
    else if b = "foo" then 
        1
    else
        compare a b

Seq.sortWith sort strings
|> Seq.iter (printfn "%s")

// Prints:
// foo
// bar
// bat
// baz
// hello
// world

Sorting a list of objects by one property and then by another

We've seen how to create a custom string sorting algorithm with F#, so now let's shift gears and talk about using Seq.sortWith to implement C#'s "sort by X then by Y" LINQ feature that is sorely missing from F#. To set the scene, let's say you have a list of orders that looks like this:

[
    { "Id": 1,
      "Amount": 100,
      "Updated": "2022-11-18",
      "Status": "shipped" },
    { "Id": 2,
      "Amount": 50,
      "Updated": "2022-11-18",
      "Status": "fulfilling" },
    { "Id": 3,
      "Amount": 85,
      "Updated": "2022-11-09",
      "Status": "fulfilling" },
    { "Id": 4,
      "Amount": 50,
      "Updated": "2022-11-11",
      "Status": "shipped" },
    { "Id": 5,
      "Amount": 100,
      "Updated": "2022-11-15",
      "Status": "fulfilling" }
]

This dataset has several places where the values are duplicated across one or more orders, which means there are multiple layers of sorting we could use. For example, three of the orders have a status of "fulfilling", so we might want to add a second sort by their id. Two orders have an amount value of 100, and two more have a value of 50, so maybe we want to sort those by the date they were last updated, or some other arbitrary property.

In C#, this kind of "sort first by X property and then by Y property" is simple when you use LINQ. If we wanted to implement that second scenario -- sorting the orders by their amount and then by the date they were last updated -- we'd do this:

var sortedOrders = orders.SortBy(o => o.Amount)
    .ThenBy(o => o.Updated)
    .ToList();

These three lines of code would sort the list by the amount (low to high) and then -- for each duplicate amount -- it would sort the duplicates by their Updated value (low to high, i.e. oldest to newest). Our list of orders would look like this:

[
    { "Id": 4,
      "Amount": 50,
      "Updated": "2022-11-11",
      "Status": "shipped" },
    { "Id": 2,
      "Amount": 50,
      "Updated": "2022-11-18",
      "Status": "fulfilling" },
    { "Id": 3,
      "Amount": 85,
      "Updated": "2022-11-09",
      "Status": "fulfilling" },
    { "Id": 5,
      "Amount": 100,
      "Updated": "2022-11-15",
      "Status": "fulfilling" },
    { "Id": 1,
      "Amount": 100
      "Updated": "2022-11-18",
      "Status": "shipped" }
]

However, in F# we don't have a built-in Seq.thenBy function to perform that second sort. We can only do the first sort by the amount:

let sortedOrders = Seq.sortBy (fun o -> o.Amount) orders

Most likely this is because lists, sequences and arrays are immutable and have no way to "remember" what the last method was. In addition, our List, Seq and Array functions are chainable but not in the same sense that LINQ methods are chainable. Our functions chain full lists from one function to another, whereas LINQ builds up a "query state" with each method call but doesn't execute that query until a method like ToList is called.

So, how do we implement the missing "sort by X then by Y" algorithm in F#? Much like our custom string sorting algorithm, it all starts with the Seq.sortWith function. Let's start simple, like we did with the string sorting, and just sort orders with an amount of 85 to the top of the list:

type Order = {
    Id: int
    Amount: int
    Updated: string
    Status: string
}

let orders = [
    { Id = 1
      Amount = 100
      Updated = "2022-11-18"
      Status = "shipped" }
    { Id = 2
      Amount = 50
      Updated = "2022-11-18"
      Status = "fulfilling" }
    { Id = 3
      Amount = 85
      Updated = "2022-11-09"
      Status = "fulfilling" }
    { Id = 4
      Amount = 50
      Updated = "2022-11-11"
      Status = "shipped" }
    { Id = 5
      Amount = 100
      Updated = "2022-11-15"
      Status = "fulfilling" }
]

let sort (a: Order) (b: Order) =
    if a.Amount = 85 then
        -1
    else
        1

Seq.sortWith sort orders
|> Seq.iter (printfn "%A")

// Prints:
// { Id = 3
//   Amount = 85
//   Updated = "2022-11-09"
//   Status = "fulfilling" }
// { Id = 1
//   Amount = 100
//   Updated = "2022-11-18"
//   Status = "shipped" }
// { Id = 2
//   Amount = 50
//   Updated = "2022-11-18"
//   Status = "fulfilling" }
// { Id = 4
//   Amount = 50
//   Updated = "2022-11-11"
//   Status = "shipped" }
// { Id = 5
//   Amount = 100
//   Updated = "2022-11-15"
//   Status = "fulfilling" }

Adding arbitrary sorting rules is as easy with records as it is with strings thanks to the Seq.sortWith function, but the example above isn't exactly doing that "sort by X then by Y" stuff we wanted.

To support that, we'll need to modify signature of our sort function so that it takes a different function as an argument. This second function, which we'll just call the "field selector" function, is what the caller will use to select arbitrary fields for sorting the orders.

There's a little bit of a trick here, though: we need to add a generic constraint that says whatever field is being selected by the field selector function, it needs to support comparisons. You see, compare isn't just for strings. It can compare anything in .NET as long as the underlying type supports comparisons. Record types, union types, tuples and more support comparisons by default in F#, which means compare will work in most cases.

This is what the constraint on the sort function should look like:

let sort<'a when 'a : comparison> (selectField: Order -> 'a) =
    failwithf "TODO: sort orders"

You'll note though that the signature no longer matches what is required by Seq.sortWith and can no longer be used as an argument for that function. To make it work again, we need the sort function to return a new function that is compatible with Seq.sortWith.

let sort<'a when 'a : comparison> (selectField: Order -> 'a) =
    fun (a: Order) (b: Order) ->
        failwithf "TODO: sort orders"

Our sort function has essentially become a wrapper around what it used to be, but now it has access to this new field selector function which we're about to use for sorting the orders by arbitrary fields! All we need to do is pass both orders to the field selector function, and the call compare on the result. That'll return an integer representing the result of the comparison (negative to shift the first order left, positive to shift it right), and Seq.sortWith will handle the rest:

let sort<'a when 'a : comparison> (selectField: Order -> 'a) =
    fun (a: Order) (b: Order) ->
        compare (selectField a) (selectField b)

Now to tie it all together, we use the updated sort by passing it an inline function which selects whichever fields you want to sort. So, to sort by the Amount field, we'd do this:

open System

type Order = {
    Id: int
    Amount: int
    Updated: string
    Status: string
}

let orders = [
    { Id = 1
      Amount = 100
      Updated = "2022-11-18"
      Status = "shipped" }
    { Id = 2
      Amount = 50
      Updated = "2022-11-18"
      Status = "fulfilling" }
    { Id = 3
      Amount = 85
      Updated = "2022-11-09"
      Status = "fulfilling" }
    { Id = 4
      Amount = 50
      Updated = "2022-11-11"
      Status = "shipped" }
    { Id = 5
      Amount = 100
      Updated = "2022-11-15"
      Status = "fulfilling" }
]

let sort<'a when 'a : comparison> (selectField: Order -> 'a) = 
    fun (a: Order) (b: Order) ->
        compare (selectField a) (selectField b)

Seq.sortWith (sort (fun o -> o.Amount)) orders
|> Seq.iter (printfn "%A")

// Prints: 
// { Id = 2
//   Amount = 50
//   Updated = "2022-11-18"
//   Status = "fulfilling" }
// { Id = 4
//   Amount = 50
//   Updated = "2022-11-11"
//   Status = "shipped" }
// { Id = 3
//   Amount = 85
//   Updated = "2022-11-09"
//   Status = "fulfilling" }
// { Id = 1
//   Amount = 100
//   Updated = "2022-11-18"
//   Status = "shipped" }
// { Id = 5
//   Amount = 100
//   Updated = "2022-11-15"
//   Status = "fulfilling" }

"Okay", you might be saying, "that lets us sort by one arbitrary field, but what about the second sort"? Well, if you can believe it, we've already implemented it. The sort function accepts generic values as long as they're comparable, which means we can pass it a tuple of fields. This works exactly how you'd expect: the first value in the tuple is the "X" field, and the second value is the "Y" field in our "sort by X then by Y".

That means, if we want to sort our list of orders first by the amount and then by the date they were updated, we'd simply pass a tuple to the sort function like so:

let sort<'a when 'a : comparison> (selectField: Order -> 'a) = 
    fun (a: Order) (b: Order) ->
        compare (selectField a) (selectField b)

Seq.sortWith (sort (fun o -> o.Amount, o.Updated)) orders
|> Seq.iter (printfn "%A")

// Prints: 
// { Id = 4
//   Amount = 50
//   Updated = "2022-11-11"
//   Status = "shipped" }
// { Id = 2
//   Amount = 50
//   Updated = "2022-11-18"
//   Status = "fulfilling" }
// { Id = 3
//   Amount = 85
//   Updated = "2022-11-09"
//   Status = "fulfilling" }
// { Id = 5
//   Amount = 100
//   Updated = "2022-11-15"
//   Status = "fulfilling" }
// { Id = 1
//   Amount = 100
//   Updated = "2022-11-18"
//   Status = "shipped" }

As you can see, the orders have been sorted differently when compared to the example directly above. They're now being sorted first by the amount -- lowest to highest -- and then, where the amounts are even, they're being sorted by the date they were last updated -- oldest to newest.

Now, I'll grant that the tuple thing isn't exactly clear unless you know that compare is being used under the hood, so you could change the signature of the sort function to explicitly ask for two fields/properties:

// Explicitly require two functions to select the fields
let sort<'left, 'right when 'left: comparison and 'right: comparison>
    (selectLeftField: Order -> 'left)
    (selectRightField: Order -> 'right)
    =
    fun (a: Order) (b: Order) -> compare (selectLeftField a, selectRightField a) (selectLeftField b, selectRightField b)

// Usage:
Seq.sortWith (sort (fun o -> o.Amount) (fun o -> o.Updated)) orders
|> Seq.iter (printfn "%A")

Just be aware that -- since generics are being used -- tuples can still be passed in with each of those selector functions. But there you have it! If you can believe it, we've just implemented our own "sort by X then by Y" in F# with those few lines of code. Although, to be fair, compare and Seq.sortWith are doing a great deal of the heavy lifting here.

If you've got any questions about custom sorting or any other F# subject, you can contact me at joshua@nozzlegear.com. I'm available for hire for freelance and consulting projects!