# Total term order

**URL:** <https://erlangforums.com/t/total-term-order/2477>\
**Category:** Proposals: RFC\
**Tags:** erlang\
**Created:** [March 20, 2023, 2:51pm UTC](https://erlangforums.com/t/total-term-order/2477 "2023-03-20T14:51:06Z")\
**Posts on this page:** 17\
**Page:** 3

<div class="post-metadata">

**Author:** ![sverker](https://erlangforums.com/user_avatar/erlangforums.com/sverker/32/841_2.png) [@sverker](https://erlangforums.com/u/sverker)\
**Post date:** [March 28, 2023, 2:42pm UTC](https://erlangforums.com/t/total-term-order/2477/43 "2023-03-28T14:42:51Z")

</div>

> [@raimo](#):
>
> > [@josevalim](#):
> >
> > (plus Erlang/OTP 26 has a different ordering for atom keys _which cannot be generalized_ because it is node specific - it only works for maps because we are responsible for their serialization/deserialization)
> 
> Oh! That should mean that maps cannot be used in keys in distributed algorithms since they compare differently on different nodes.

Maps have a defined order independent of implementation.  
The changed ordering in OTP 26 of atom keys in maps is a totally **internal** affair. The only visible effect is the **undefined traversal order** exposed by io:format, maps:iterator and the external format.

---

<div class="post-metadata">

**Author:** ![DianaOlympos](https://erlangforums.com/user_avatar/erlangforums.com/dianaolympos/32/1056_2.png) [@DianaOlympos](https://erlangforums.com/u/DianaOlympos)\
**Post date:** [March 28, 2023, 10:49pm UTC](https://erlangforums.com/t/total-term-order/2477/44 "2023-03-28T22:49:37Z")

</div>

> [@raimo](#):
>
> And I still cannot see how we could fix this bug in a safe way…

We can’t, not without a breaking change. Honestly… maybe something we have to accept, maybe by raising or warning on it. At some point, it is ok to say that old code needs work to compile on modern OTP. We broke old rebar forcing a lot of people to port it to rebar3 a few years ago after all.

To go back to the original question: Map key order, BIF, no new operators, and yes, please break or yell on comparing floats and integers. Erlang is strongly typed, and this particular behavior with floats have been a source of bugs multiple time for me.

---

<div class="post-metadata">

**Author:** ![richardc](https://erlangforums.com/user_avatar/erlangforums.com/richardc/32/1043_2.png) [@richardc](https://erlangforums.com/u/richardc)\
**Post date:** [April 3, 2023, 10:37am UTC](https://erlangforums.com/t/total-term-order/2477/47 "2023-04-03T10:37:47Z")

</div>

I’m a little concerned about the phrasing of things here, which may confuse things more than they should have to. The order defined by the operators `<`, `=<`, `>`, `>=`, `==`, and `/=` is an _arithmetic_ term order (`==` being arithmetic equality), and it **is** a total order, precisely because it does not separate integers from floats and considers the integer and float forms of the same number to be the same object. This is great for how humans work with numbers and orderings; both individual numbers as well as tuples of numbers or lists of numbers get the order you expect, and it’s total. Nothing peculiar at all about it.

Only when doing computery things is this often not what you want. In data structures we want fast comparisons on keys, and not have to consider whether we should promote an int to a float just for comparing. We probably do not care about the order between floats and ints, since ints are common as keys, while using floats as keys is rarely a good idea except for things like memoizing, and we typically want to have separate entries for `3` and `3.0`. The built-in pattern matching behaves like this, using the exact equality operators `=:=` and `=/=`.

It is when we combine `<` and ´\>´ with `=:=` that we don’t get a total order:

```
    case X of
        Y -> equal; # uses =:=
        _ when X > Y -> greater;
        _ when X < Y -> less
    end

```

if X is 3 and Y is 3.0, none of the clauses match, because we have a mix of operators. What we need is an _alternative_ total order, so we don’t end up with this mix, with the new operators `:<` and `>:`. Using these in the above code, one clause would always match, since we’d have integer() \< float() (in the map key ordering).

I don’t think the “glitch at zero” solution is something to be sad about. I have seen other functional languages do the exact same thing in order to get a total order on floats. I also think that the maps ordering on keys is quite perfect as it is, and that there is nothing weird in saying that one map is less than some other map, any more than saying one tuple `{2, 1}` is less than another tuple `{2, 2}`, given that there is an ordering on the keys.

I think that the candidate named “the exact term order” in the proposal, which would consider an integer to be infinitesimally greater than the corresponding float, would cause too many problems. For one thing, you’d get the unwanted result that converting maps into lists of keys/value pairs would produce a different order than when comparing them as maps. And for several “computery” applications, you’d want integers and floats grouped separately by a sort, so you’d have to implement yet another order anyway on top of this.

---

<div class="post-metadata">

**Author:** ![raimo](https://erlangforums.com/user_avatar/erlangforums.com/raimo/32/867_2.png) [@raimo](https://erlangforums.com/u/raimo)\
**Post date:** [April 3, 2023, 12:52pm UTC](https://erlangforums.com/t/total-term-order/2477/48 "2023-04-03T12:52:29Z")

</div>

> [@richardc](#):
>
> It is when we combine `<` and ´\>´ with `=:=` that we don’t get a total order:

Precisely. If the `=:=` and `=/=` operators had not been introduced, it would have been “impossible” (we would have to be without `is_float()` and `is_integer()` too, and match them as equal) to distinguish between a float `==` an integer. And now when we have them there is no total order they (and pattern matching) are part of.

> [@richardc](#):
>
> and that there is nothing weird in saying that one map is less than some other map, any more than saying one tuple `{2, 1}` is less than another tuple `{2, 2}`

I think it is less obvious since a tuple has got a very natural element order numbered 1…N, so defining a sort order is easy. For a data structure intended for lookup access, key order as well as sort order is uninteresting. A sort order has to be constructed/forced, and there are multiple ways with different trade-offs.

> [@richardc](#):
>
> For one thing, you’d get the unwanted result that converting maps into lists of keys/value pairs would produce a different order than when comparing them as maps.

If that had been the case, the map key order would have been a stronger contestant for me. But now to sort maps by converting them to simpler terms, since they are sorted on size first then keys before values, I suppose you would have to use something like:

```erlang
MX =
    lists:unzip(
        lists:sort(
            fun (KV1, KV2) -> element(1, KV1) =:< element(1, KV2) end,
            maps:to_list(M)),
{list_to_tuple(element(1, MX), list_to_tuple(element(2, MX))

```

and then compare these terms according to the _maps key order_.  
That conversion is unfortunately not as useful as `maps:to_list(M)`.

---

<div class="post-metadata">

**Author:** ![nzok](https://erlangforums.com/letter_avatar_proxy/v4/letter/n/4af34b/32.png) [@nzok](https://erlangforums.com/u/nzok)\
**Post date:** [April 6, 2023, 12:05pm UTC](https://erlangforums.com/t/total-term-order/2477/50 "2023-04-06T12:05:28Z")

</div>

It is important to have comparison operations that behave themselves sensibly  
for numbers.

It is useful to have a total order on terms.

But what are the fundamental requirements for ordering?  
(1) X =\< X  
(2) X =\< Y and Y =\< Z implies X =\< Z  
(3) X =\< Y and Y =\< X implies X equals Z  
(4) X =\< Y or Y =\< X  
(5) X equals X  
(6) X equals Y and Y equals Z implies X equals Z.

Modulo some rather desperate hand-waving over “equals”,  
this is true of the arithmetic order. The equivalence  
induced by =\< in Erlang puts {0,-0.0,0.0} in the same  
equivalence class, but that’s OK.

When one of X,Y is exact (an integer, say) and the  
other is inexact (a float, say), it is important to  
compare them by converting the inexact number to an  
exact one rather than the other way around. Otherwise  
you can easily break (6).

But we’re not talking about total orders in general  
at this point, but an ARITHMETIC total order. And for  
those we have expectations like  
(7) X - Y equals 0 implies X equals Y.  
And here, I’m afraid, Erlang’s arithmetic order fails.

Consider X = 2 **55 + 1, Y = 2.0** 55.  
Then X-Y == 0 but it is not true that X == Y.

Ada and Haskell forbid mixing integers and floats  
without explicit conversions. It’s a very good idea,  
even for dynamic programming languages.

The problem comes when we confuse arithmetic equality  
with identity. We expect that for any pure F,  
(8) X equals Y implies F(X) equals F(Y)  
and that just isn’t true in Erlang for several  
built-in F when equals is taken to be == .

We are driven to the conclusion that  
the arithmetic ordering in Erlang  
IS a total order  
but is NOT an arithmetic total order.  
due in large part to mashing up integers and floats.

As for the term order, the only thing that really really matters  
is that ALL uses of it be CONSISTENT with the rules and with each  
other.

It is important to compare ex

---

<div class="post-metadata">

**Author:** ![nzok](https://erlangforums.com/letter_avatar_proxy/v4/letter/n/4af34b/32.png) [@nzok](https://erlangforums.com/u/nzok)\
**Post date:** [April 7, 2023, 11:42pm UTC](https://erlangforums.com/t/total-term-order/2477/51 "2023-04-07T23:42:08Z")

</div>

Curse this formatted mail nonsense!  
Consider X = 2 **55 + 1, Y = 2.0** 55.  
Was, of course, X = 2 “raised to the power” 55 + 1,  
Y = 2.0 “raised to the power” 55.

---

<div class="post-metadata">

**Author:** ![raimo](https://erlangforums.com/user_avatar/erlangforums.com/raimo/32/867_2.png) [@raimo](https://erlangforums.com/u/raimo)\
**Post date:** [April 11, 2023, 10:26am UTC](https://erlangforums.com/t/total-term-order/2477/52 "2023-04-11T10:26:06Z")

</div>

I confirm the behaviour:

```erlang
1> X = 1 bsl 53.
9007199254740992
2> Y = float(X).
9.007199254740992e15
3> Z = X + 1.
9007199254740993
4> X - Y == 0.
true
5> X == Y.
true
6> Z - Y == 0.
true
7> Z == Y.
false

```

I would say that

> [@nzok](#):
>
> (7) X - Y equals 0 implies X equals Y.

is an assumption about arithmetic operations that we cannot expect to hold for the arithmetic model that we have.

Floating point values are exact, but floating point operations may be inexact.

Even a simple operation like `Z - Y` may cause rounding that produces exactly `0.0`, while the values of `Z` and `Y` do not compare equal. In this case it is the implicit conversion from integer to float of `Z` that rounds off one bit.

The floating point value 2.0^53 (`math:pow(2.0, 53)`) has got an exact value that is equal to the integer `1 bsl 53` and should not be equal to any other integer. Therefore the floating point value is converted to an exact integer representation when being compared to an integer, if possible, to not break your (6), as you say.

I would say that the arithmetic ordering in Erlang IS an arithmetic total order, but floating point **operations** such as automatic conversion from integer to float may cause rounding errors.

---

<div class="post-metadata">

**Author:** ![juhlig](https://erlangforums.com/user_avatar/erlangforums.com/juhlig/32/837_2.png) [@juhlig](https://erlangforums.com/u/juhlig)\
**Post date:** [March 27, 2025, 8:49am UTC](https://erlangforums.com/t/total-term-order/2477/53 "2025-03-27T08:49:35Z")

</div>

Say… did anything come out of this proposal? 😅

---

<div class="post-metadata">

**Author:** ![juhlig](https://erlangforums.com/user_avatar/erlangforums.com/juhlig/32/837_2.png) [@juhlig](https://erlangforums.com/u/juhlig)\
**Post date:** [March 27, 2025, 11:41am UTC](https://erlangforums.com/t/total-term-order/2477/54 "2025-03-27T11:41:22Z")

</div>

On a related but different topic: wouldn’t it be a good idea to have a `compare` function alongside the comparison operators, which would return whether the first argument is `less`, `equal` or `greater` than the second? Something like…

```erlang
compare(X, Y) when X < Y ->
    less;
compare(X, Y) when X > Y ->
    greater;
compare(_X, _Y) ->
    equal.

```

… only as a more efficient BIF. AFAICT, there is already something like that, internally.

Where could this be useful? If I look at the `lists:usort/1` code for example, I see many occurences of “… is `X>Y`? if not, is `X==Y`? …”, that is, two comparisons are necessary if `X=<Y`. If `X` and `Y` are for example long lists which are equal or only differ in their last elements, comparisons are expensive because all elements up to the first different one are compared. And in (u)sorting, comparisons are done a lot.

---

<div class="post-metadata">

**Author:** ![mikpe](https://erlangforums.com/letter_avatar_proxy/v4/letter/m/b487fb/32.png) [@mikpe](https://erlangforums.com/u/mikpe)\
**Post date:** [March 27, 2025, 12:15pm UTC](https://erlangforums.com/t/total-term-order/2477/55 "2025-03-27T12:15:39Z")

</div>

> Where could this be useful? If I look at the `lists:usort/1` code for example, I see many occurences of “… is `X>Y`? if not, is `X==Y`? …”, that is, two comparisons are necessary if `X=<Y`. If `X` and `Y` are for example long lists which are equal or only differ in their last elements, comparisons are expensive because all elements up to the first different one are compared. And in (u)sorting, comparisons are done a lot.

The compiler should be able to compile clauses that only differ in such term comparison expressions into a single `cmp` call.

I’m not sure I’d want to lift that into the language though.

> if X \> Y → A; X \< Y → B; true → C end

is better IMO than

> case cmp(X, Y) of greater → A; less → B; \_ → C end

---

<div class="post-metadata">

**Author:** ![juhlig](https://erlangforums.com/user_avatar/erlangforums.com/juhlig/32/837_2.png) [@juhlig](https://erlangforums.com/u/juhlig)\
**Post date:** [March 27, 2025, 2:48pm UTC](https://erlangforums.com/t/total-term-order/2477/56 "2025-03-27T14:48:11Z")

</div>

The problem with compiler optimization magic is that it is largely undocumented, including the circumstances when it will (not) happen. The preconditions may change only so slightly, or the optimization might be gone altogether tomorrow.

Aside from that, I agree that the first looks better than the second 😉

---

<div class="post-metadata">

**Author:** ![nzok](https://erlangforums.com/letter_avatar_proxy/v4/letter/n/4af34b/32.png) [@nzok](https://erlangforums.com/u/nzok)\
**Post date:** [March 31, 2025, 9:55am UTC](https://erlangforums.com/t/total-term-order/2477/57 "2025-03-31T09:55:14Z")

</div>

case compare x y of  
LT → …  
GT → …  
EQ → …  
is how you would do it in Haskell; I really cannot see the two-comparison version as anything other than an ugly approximation to this.  
I was and am a big fan of compare/3 in Prolog and never did understand why Erlang didn’t pick this up.

---

<div class="post-metadata">

**Author:** ![Maria-12648430](https://erlangforums.com/user_avatar/erlangforums.com/maria-12648430/32/604_2.png) [@Maria-12648430](https://erlangforums.com/u/Maria-12648430)\
**Post date:** [April 1, 2025, 10:14am UTC](https://erlangforums.com/t/total-term-order/2477/58 "2025-04-01T10:14:48Z")

</div>

Now that you put it _that_ way… 😄

For me, I think both _notations_ (!) have their merits.

The two (or three, if you want to be really strict) -comparison way makes it pretty clear, even without looking at the surrounding (`compare...`) context, when what will happen.

The `compare` notation is by and large just as good, depending on circumstances possibly even more expressive. Depending on circumstances again, possibly less.

That said, I would like to have the choice of both.

* * *

When it comes to _runtime characteristics_ such as what we generally term “performance”, it is pretty clear _just from looking at it_ that the `compare` approach can go with less actual comparison work than the multi-comparison one.

The compiler may be able to massage the latter to be like the former performance-wise, but unless you know about it, the latter (“tell me how the first argument compares to the second”) always at least _looks_ inferior to the former (“tell me if the first argument is less than the second, and if not tell me if the first argument is equal to the second”).

Compiler optimizations (not) happening in the background without anybody (at the user level) knowing about them is always a fickle thing. Small changes in the code may stop them from happening, or they may be all gone by tomorrow because they got in the way of something.

That said, _I_ prefer something that is _reliably slow_ over something that _may be fast_ if the stars are right any day 🤷‍♀️

> [@nzok](#):
>
> why Erlang didn’t pick this up

Maybe @raimo and/or @bjorng can shed some light on the background here? \*poke\*

---

<div class="post-metadata">

**Author:** ![nzok](https://erlangforums.com/letter_avatar_proxy/v4/letter/n/4af34b/32.png) [@nzok](https://erlangforums.com/u/nzok)\
**Post date:** [April 2, 2025, 3:49am UTC](https://erlangforums.com/t/total-term-order/2477/59 "2025-04-02T03:49:35Z")

</div>

The thing about “compare” is that it is intention-revealing.  
if X \< Y →   
; Y \< X-\>  
; true →   
end  
is not particularly intention-revealing. You have to read it carefully. It is easy to get  
wrong (the first time I typed the example about the second line read “; X \< Y” oops).  
There are arbitrary choices to be made. For example,  
if X =:= Y →   
; x \< Y →   
; true →   
end  
might be marginally faster: when comparing two atoms =:= can fail fast; when comparing two  
tuples or binaries =:= can fail fast if they are different lengths. And there is the  
choice I always find confusing in Erlang, whether to use =:= or == or make it less  
efficient and put it as the default. With “compare” there is one obvious way to do it.

What’s more, the “compare” approach can be extended in a natural way to comparisons  
(such as IEEE floating-point comparisons) where there is a fourth possibility, order  
undefined.

Ignoring the =:= vs == question, I can think of about 20 different ways to express  
“A if X \< Y or B if X \> Y or C if X = Y” using 2-way comparisons, with slight but  
detectable performance differences.

Mind you, I’ve been burned a few times by languages where testing whether  
X =\< Y runs you into “not(Y \< X)” and (X \< Y or X = Y) can give different answers.

---

<div class="post-metadata">

**Author:** ![Maria-12648430](https://erlangforums.com/user_avatar/erlangforums.com/maria-12648430/32/604_2.png) [@Maria-12648430](https://erlangforums.com/u/Maria-12648430)\
**Post date:** [April 2, 2025, 11:57am UTC](https://erlangforums.com/t/total-term-order/2477/60 "2025-04-02T11:57:41Z")

</div>

> [@nzok](#):
>
> The thing about “compare” is that it is intention-revealing.

I don’t disagree 😉

It’s not an _either-_ this-way-or-that question, too. `compare` would not stand in the way of using `<`/`==`/`>` and vice versa, so a user could chose whichever (he thinks) best fits a particular use case.

Only awkward thing I see is that, given that we do have `==` and `=:=` (and maybe `:<` etc coming), we would also need a strict (`=:=`-ish) and a non-strict (`==`-ish) version of `compare` 🤷‍♀️

---

<div class="post-metadata">

**Author:** ![raimo](https://erlangforums.com/user_avatar/erlangforums.com/raimo/32/867_2.png) [@raimo](https://erlangforums.com/u/raimo)\
**Post date:** [April 2, 2025, 12:31pm UTC](https://erlangforums.com/t/total-term-order/2477/61 "2025-04-02T12:31:03Z")

</div>

And maybe also the maps key order version

---

<div class="post-metadata">

**Author:** ![uwiger](https://erlangforums.com/user_avatar/erlangforums.com/uwiger/32/274_2.png) [@uwiger](https://erlangforums.com/u/uwiger)\
**Post date:** [August 11, 2026, 7:29am UTC](https://erlangforums.com/t/total-term-order/2477/62 "2026-08-11T07:29:55Z")

</div>

BTW, I did look briefly at making `sext` support native records. I think I found a way, even if a bit quirky. However, I would argue that native records should not be used for key encoding where the keys need to be sorted.

As I understand it, native records sort primarily on module names and then on the data. This alone makes the sorting a bit odd for database purposes, and also blows up the encoding (the module name has to be included). Finally, for the record to be decoded, the module has to exist everywhere.

If someone would still need it, the quirk is that it has to be squeezed in between tuples (first byte: 16) and lists (first byte: 17). After cursing the choice of not having left room for new types in the space between tuples and lists, I already had to do this for maps:

```erlang
decode_next(<<?list, 1, Rest/binary>>) -> decode_map(Rest);

```

Now, I didn’t leave a whole lot of room for more subtypes before maps, but `<<?list, 0, ...>>` is available, and I was thinking that perhaps this should simply extend to a ‘pre-map type’, for the event that @bjorng comes up with even more native types. 😉

[Previous page](https://erlangforums.com/t/total-term-order/2477.md?page=2)