I want nothing fancy: a sort function (from a library), taking for arguments a list or a vector (of strings, in my case) and a comparator which I want to write myself according to my needs.

The comparators are described here. They take two arguments, and return comparison, which consists of three values: lesser, greater, and equivalent. It looks like what I need, but I can't find a sort function to feed my custom comparator to.

The ācomparatorā that you mentioned is not a part of Racket. Itās part of a user package called Rebellion, created by @notjack, and you need to additionally install the package to use it.

If you want to use Rebellion, the sort functionality that you are looking for is the sorting transducer.

If you want to use pure Racket, the standard sort function would be sort. It accepts a comparator as a second argument, although this comparator has a different signature than the one in Rebellion: it should return a boolean, indicating whether the first element is less than the second element.

That's a great question! Why don't you think about it a bit more? If someone gives you a boolean comparator, can you construct a three-way comparator? What about the other direction?

More accurately, Boolean predicates are embedded in three-way comparators. The reason is in the typesāa three-way comparator has as its range a sum type with three nullary constructors (letās use Haskell syntax for this)

data Ordering = LT | EQ | GT

while a Boolean predicate has as its range, well, a Boolean type, which is a sum type with two nullary constructors

data Bool = True | False

We can think of how to map back and forth between them. Suppose I have a three-way comparator, I can construct three Boolean predicates out of this (letās identify them with their negated counterparts) with the maps

[LT ā¦ True, EQ ā¦ False, GT ā¦ False], this is āless thanā;

[LT ā¦ False, EQ ā¦ True, GT ā¦ False], this is āequal toā;

[LT ā¦ False, EQ ā¦ False, GT ā¦ True], this is āgreater thanā.

As can be seen, three-way comparators are more informative than Boolean predicates, which is why we have an embedding at hand, not an isomorphism. Correspondingly, we can also construct three-way comparators from Boolean predicates by inversion of the above maps, but this is more unfortunate because False will end up corresponding to two cases, and we donāt know which! What can that possibly mean? That means weāve lost information (or proofs, as proof theorists will point out) by going back and forth.

Okay, type-theoretic nonsense aside, the reason sort doesnāt need a three-way comparator is indeed that it only needs to know about āless thanā (or, unsurprisingly, āgreater thanā). It all depends on which interpretation you want.

I think it might help to see a worked-out example in Racket:

#lang typed/racket
(: 2to3 (ā [Ī±] (-> (-> Ī± Ī± Boolean)
(-> Ī± Ī± (U '< '= '>)))))
(define ((2to3 <) a b)
(cond
[(< a b)
'<]
[(< b a)
'>]
[else
'=]))
(: 3to2 (ā [Ī±] (-> (-> Ī± Ī± (U '< '= '>))
(-> Ī± Ī± Boolean))))
(define ((3to2 cmp) a b)
(eq? '< (cmp a b)))

Note that 3to2 in my example isn't the same as Python's functools.cmp_to_key(), from what I understand from its docs.

In Racket, we have various comparison functions, each of which defines a domain of values which it can compare and a notion of ordering: for example, string<?, string-ci<?, string>?, string-locale<?, and string-locale-ci<? (among others) all define different orders for sorting strings.

In contrast, Python values have a built-in notion of ordering according to the <, <=, ==, !=, >=, and > operators, which can be customized using the special __lt__(), __le__(), __eq__(), __ne__(), __gt__(), and __ge__() methods. For Python APIs that use a "key function", sorting is customized by returning a wrapper/replacement object where the built-in comparison operators implement the desired order, rather than, as in Racket, supplying a different function to use for sorting. I haven't looked at the implementation, but I would imagine functools.cmp_to_key() works by returning wrapper objects that use the provided three-way comparison function to implement the comparison methods. So 3to2 in my example would be like the implementation of __lt__() on the wrapper object, not like functools.cmp_to_key() as a whole.