# Custom sort with a comparator **URL:** \ **Category:** Questions & Answers\ **Created:** [March 26, 2024, 5:13pm UTC](https://racket.discourse.group/t/custom-sort-with-a-comparator/2839 "2024-03-26T17:13:23Z")\ **Posts on this page:** 8\ **Page:** 1
**Author:** ![Tyrn](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/tyrn/32/1731_2.png) [@Tyrn](https://racket.discourse.group/u/Tyrn)\ **Post date:** [March 26, 2024, 5:13pm UTC](https://racket.discourse.group/t/custom-sort-with-a-comparator/2839/1 "2024-03-26T17:13:23Z")
Hi, 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](https://docs.racket-lang.org/rebellion/Comparators.html). 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. ---
**Author:** ![sorawee](https://avatars.discourse-cdn.com/v4/letter/s/ea5d25/32.png) [@sorawee](https://racket.discourse.group/u/sorawee)\ **Post date:** [March 26, 2024, 5:31pm UTC](https://racket.discourse.group/t/custom-sort-with-a-comparator/2839/2 "2024-03-26T17:31:15Z")
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](https://docs.racket-lang.org/rebellion/Transducers.html#%28def._%28%28lib._rebellion%2Fstreaming%2Ftransducer..rkt%29._sorting%29%29). If you want to use pure Racket, the standard sort function would be [sort](https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28lib._racket%2Fprivate%2Flist..rkt%29._sort%29%29). 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. ---
**Author:** ![Tyrn](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/tyrn/32/1731_2.png) [@Tyrn](https://racket.discourse.group/u/Tyrn)\ **Post date:** [March 26, 2024, 5:50pm UTC](https://racket.discourse.group/t/custom-sort-with-a-comparator/2839/3 "2024-03-26T17:50:05Z")
Any idea why do these two approaches exist? The boolean comparator isn't just as universal, or is it? ---
**Author:** ![sorawee](https://avatars.discourse-cdn.com/v4/letter/s/ea5d25/32.png) [@sorawee](https://racket.discourse.group/u/sorawee)\ **Post date:** [March 26, 2024, 6:22pm UTC](https://racket.discourse.group/t/custom-sort-with-a-comparator/2839/4 "2024-03-26T18:22:56Z")
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? ---
**Author:** ![Tyrn](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/tyrn/32/1731_2.png) [@Tyrn](https://racket.discourse.group/u/Tyrn)\ **Post date:** [March 27, 2024, 5:05am UTC](https://racket.discourse.group/t/custom-sort-with-a-comparator/2839/5 "2024-03-27T05:05:22Z")
> [@sorawee](#): > > That's a great question! Totally agree. As a matter of fact, it mystifies me for years. Let's see what we have. 1. Why boolean comparators? Because we can use standard boolean predicates for a comparator, which is enough in common cases. 2. Can we construct a three-way comparator out of a boolean one? This is trivial, unless I misunderstand the question. 3. Can we feed a three-way comparator to a function which requires a boolean one? Yes, we (can?), but here the black magic starts (for me). A working example, Python. `_path_compare()` is an "old style", as they call it, three-way comparator. `functools.cmp_to_key()` is the black magic. ```scheme lst = os.listdir(src) dirs = sorted( [Path(x) for x in lst if (src / x).is_dir()], key=functools.cmp_to_key( (lambda xp, yp: _path_compare(yp, xp)) if _ARGS.reverse else _path_compare ), ) ``` Why and how they banned the three-way comparators, beats me. [The Python docs](https://docs.python.org/3/library/functions.html#sorted). So far I hoped to get away with my ignorance 😊 ... ---
**Author:** ![usao](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/usao/32/1375_2.png) [@usao](https://racket.discourse.group/u/usao)\ **Post date:** [March 27, 2024, 6:20am UTC](https://racket.discourse.group/t/custom-sort-with-a-comparator/2839/6 "2024-03-27T06:20:27Z")
More accurately, Boolean predicates are [_embedded_](https://ncatlab.org/nlab/show/embedding) 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) ```haskell 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 ```haskell 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 1. `[LT ↦ True, EQ ↦ False, GT ↦ False]`, this is “less than”; 2. `[LT ↦ False, EQ ↦ True, GT ↦ False]`, this is “equal to”; 3. `[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. ---
**Author:** ![soegaard](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/soegaard/32/19_2.png) [@soegaard](https://racket.discourse.group/u/soegaard)\ **Post date:** [March 27, 2024, 4:48pm UTC](https://racket.discourse.group/t/custom-sort-with-a-comparator/2839/7 "2024-03-27T16:48:34Z")
The rationale for srfi 67 "Compare Procedures" has a section on 2-way vs 3-way comparisons. [https://srfi.schemers.org/srfi-67/srfi-67.html#node\_sec\_6](https://srfi.schemers.org/srfi-67/srfi-67.html#node_sec_6) ---
**Author:** ![LiberalArtist](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/liberalartist/32/151_2.png) [@LiberalArtist](https://racket.discourse.group/u/LiberalArtist)\ **Post date:** [March 27, 2024, 7:57pm UTC](https://racket.discourse.group/t/custom-sort-with-a-comparator/2839/8 "2024-03-27T19:57:53Z")
> [@Tyrn](#): > > Can we feed a three-way comparator to a function which requires a boolean one? Yes, we (can?), but here the black magic starts (for me). I think it might help to see a worked-out example in Racket: ```scheme #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))) ``` > [@Tyrn](#): > > `functools.cmp_to_key()` is the black magic Note that `3to2` in my example isn't the same as Python's [`functools.cmp_to_key()`](https://docs.python.org/3/library/functools.html#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-locale=`, 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.