Add comparison combinators for sorting to the standard library

[vkleen]

In a recent Nickel hour we would have found use for a corpus of comparison functions and combinators. For context, the array.sort function in the standard library takes as the first parameter a function of type a -> a -> [| `Lesser, `Equal, `Greater |], which is supposed to perform the comparison operation during the sort.

Currently, users of array.sort are required to write this function by hand. We would instead like to add comparison functions to the standard library to compare types for which there is a reasonable default:

• num.compare should use the builtin < operator
• string.compare should use lexicographic string comparison

Additionally, we would like combinators to build more complex comparison functions, e.g.

• array.lexicographically f to lexicographically compare arrays with the preexisting comparison function f
• record.on field f to compare records containing a certain field by applying a preexisting comparison function f to that field only

[aspiwack]

This is not necessarily directly relevant for Nickel, but I would like to point out the remarkable monoid instance for Ordering in Haskell.

The gist is

Eq <> o = o
o <> _ = o

This correspond to lexicographic ordering. But it shines when combined with the monoid instance for a -> b (which is defined pointwise).

For instance, here is a definition of the lexical ordering on pairs:

 (compare `on` fst) <> (compare `on` snd)

(Now, the on function is itself a remarkable little hack which could be useful for such a library)

---

Anyway, there are some hidden gems of the sort in Haskell's library. Unfortunately, they're not really all in a conveniently accessible place, but you'll find some of them in Data.Ord. It may be worth looking there for inspiration.

[jeremyschlatter]

I opened a PR with implementations of the functions suggested here.

The PR uses array.compare_with instead of array.lexicographically because that seemed clearer to me.

Also, I happily noticed that record.on is more general than I expected. In record.on field f, f can be a -> a -> b for any b, not just a -> a -> [| 'Lesser, 'Equal, 'Greater |]