# Meaning of \`isless\`, \`\<\`, \`cmp\`, \`isequal\`, \`==\`, total order, partial order, unordered

**URL:** <https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176>\
**Category:** Internals & Design\
**Created:** [January 5, 2018, 2:25pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176 "2018-01-05T14:25:19Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![klacru](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/klacru/32/27890_2.png) [@klacru](https://discourse.julialang.org/u/klacru)\
**Post date:** [January 5, 2018, 2:25pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/1 "2018-01-05T14:25:19Z")

</div>

Is there a definitive expanation or definition of those terms with respect to Julia?

I thougth I had a clear understanding, but am a little bit unsettled after I saw `cmp(::AbstractArray, ::AbstractArray)` and the documentation of `cmp(::AbstractString, ::AbstractString)`.  
See [#25401](https://github.com/JuliaLang/julia/pull/25401) and [#25407](https://github.com/JuliaLang/julia/issues/25407).

---

<div class="post-metadata">

**Author:** ![jeff.bezanson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeff.bezanson/32/48_2.png) [@jeff.bezanson](https://discourse.julialang.org/u/jeff.bezanson)\
**Post date:** [January 5, 2018, 3:40pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/2 "2018-01-05T15:40:18Z")

</div>

The string case is just a simple mistake in the doc string.

Until yesterday, arrays never supported `isless`. I blindly renamed `lexless` for arrays to `isless`, problem being it does not look at the shape. I think some good options are (1) restrict it to vectors, or (2) end the function by calling `cmp(size(A), size(B))` instead of `cmp(length(A), length(B))`.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [January 5, 2018, 4:00pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/3 "2018-01-05T16:00:11Z")

</div>

Another option would be to do lexicographical ordering on elements in linear ordering (so column major for dense arrays) but error if `size(A) != size(B)`.

---

<div class="post-metadata">

**Author:** ![klacru](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/klacru/32/27890_2.png) [@klacru](https://discourse.julialang.org/u/klacru)\
**Post date:** [January 5, 2018, 4:00pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/4 "2018-01-05T16:00:57Z")

</div>

I think, we should stick to the existing documentation and define `isless`, `cmp` only, if the arguments have the same type and the type has a natural, general, agreed, and commonly expected (canonical) total order.

That is IMO not the case for any `AbstractArray`, also not for `Vector`, even if they have the same shape.  
For vectors, I could imagine a kind of lexical ordering similar to `AbstractString`. That would be a total order, but is not canonical. Who would sort cartesian coordinate vectors lexicographically?

Calling `cmp(size(A), size(B))` would end in a discussion about comparison of tuples.

Stefan’s option would be the best approach, but not resolve my objections.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [January 5, 2018, 4:03pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/5 "2018-01-05T16:03:19Z")

</div>

The issue with that is that we ended up having these `lexless` and `lexcmp` functions hanging around even though we don’t have any behavior defined for arrays for `isless` or `cmp` anyway. It just seems pointless not to define `isless` and `cmp` for arrays in the only way we provide to order them.

---

<div class="post-metadata">

**Author:** ![klacru](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/klacru/32/27890_2.png) [@klacru](https://discourse.julialang.org/u/klacru)\
**Post date:** [January 5, 2018, 4:30pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/6 "2018-01-05T16:30:08Z")

</div>

That is not an argument. If we define `isless` in a certain way we suggest to the user, that it is “The canonical total order” of the type. That is not the case for vectors and lexicographic. Rather it would be better to keep `islexless` and `lexcmp` to indicate to the user, that he is not using a canonical order.

With the same argument we could define `isless` and `cmp` for sets, because it is easy to construct a lexical order for sets of (totally) ordered element types, but the canonical order for sets is and remains the partial order implied by set-inclusion.

---

<div class="post-metadata">

**Author:** ![klacru](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/klacru/32/27890_2.png) [@klacru](https://discourse.julialang.org/u/klacru)\
**Post date:** [January 5, 2018, 4:46pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/7 "2018-01-05T16:46:24Z")

</div>

In the `sort` functions it is possible to use any user-provided ordering by the `lt` argument. Would it make sense to extend this use to `max` and all other functions, which rely on `isless` to be defined?

It would also be possible to attach user-defined comparison behaviour to user defined types. And - one of my favorite ideas - make user defined subtypes of arrays possible? Yes - I think about inheritance from concrete types, which adds no state, but allows methods to dispatch on the subtype.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [January 5, 2018, 8:49pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/8 "2018-01-05T20:49:50Z")

</div>

> [@StefanKarpinski](#):
>
> The issue with that is that we ended up having these lexless and lexcmp functions hanging around even though we don’t have any behavior defined for arrays for isless or cmp anyway. It just seems pointless not to define isless and cmp for arrays in the only way we provide to order them.

I can see the argument that it is more useful to define a default `isless` function than to leave it undefined, even if the choice of ordering is ambiguous. That way things like `sort` will at least give _some_ reasonable ordering, and the user can always specify a different ordering manually.

But by the same argument, shouldn’t we also define an `isless(::Complex, ::Complex)` method via lexicographical ordering? ( ~~It will have the essentially same algebraic drawbacks as lexicographical ordering of arrays.~~ Not quite, because arrays don’t define `*`, see below.)

We still shouldn’t define `<` for arrays or complex numbers, of course: I would say that `<` should be reserved for cases where there is an unambiguous standard ordering (not including NaN).

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [January 5, 2018, 8:52pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/9 "2018-01-05T20:52:21Z")

</div>

Sure, that seems reasonable to me. I wonder if polar ordering for complex numbers isn’t the more commonly useful one though. Isn’t that how complex eigenvalues are usually sorted? OTOH, I guess that lexicographical ordering has the advantage of being simpler and more obvious. As long as we provide polar ordering functions, it’s easy enough to ask for.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [January 5, 2018, 8:58pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/10 "2018-01-05T20:58:17Z")

</div>

> [@StefanKarpinski](#):
>
> Isn’t that how complex eigenvalues are usually sorted?

Complex eigenvalues aren’t usually sorted 😉. In [#21598](https://github.com/JuliaLang/julia/pull/21598) I suggested sorting them lexicographically.

---

<div class="post-metadata">

**Author:** ![jeff.bezanson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeff.bezanson/32/48_2.png) [@jeff.bezanson](https://discourse.julialang.org/u/jeff.bezanson)\
**Post date:** [January 5, 2018, 9:05pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/11 "2018-01-05T21:05:05Z")

</div>

`sortrows` sorts lexicographically, so there’s at least some precedent for comparing arrays lexicographically by default.

> [@stevengj](#):
>
> We still shouldn’t define \< for arrays

About that… `<` has a fallback that calls `isless`; maybe we should remove it?

Defining a default ordering for complex numbers sort of rubs me the wrong way. I think because they’re so similar to objects that have an ordering, and yet they don’t.

---

<div class="post-metadata">

**Author:** ![klacru](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/klacru/32/27890_2.png) [@klacru](https://discourse.julialang.org/u/klacru)\
**Post date:** [January 5, 2018, 9:12pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/12 "2018-01-05T21:12:42Z")

</div>

The purpose of this thread was to settle a solid fundament on how we treat ordering in Julia. In the moment it looks like we are throwing everything away, we had already as a consensus:

isless defined \<=\> there is a canonical order inherent in the type

That is not the case for complex or vectors or arrays.  
Sorting is not a justification to define isless, because there is this lt named argument for non-standard wishes.

---

<div class="post-metadata">

**Author:** ![jeff.bezanson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeff.bezanson/32/48_2.png) [@jeff.bezanson](https://discourse.julialang.org/u/jeff.bezanson)\
**Post date:** [January 5, 2018, 9:19pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/13 "2018-01-05T21:19:48Z")

</div>

We have also long had an `isless` method for tuples that uses lexicographical ordering…

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [January 5, 2018, 10:07pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/14 "2018-01-05T22:07:30Z")

</div>

> [@jeff.bezanson](#):
>
> We have also long had an isless method for tuples that uses lexicographical ordering…

Tuples are different because they don’t support `+`.

The problem with defining `<` for ~~arrays or~~ complex numbers is that there is no way to do it that this consistent with addition (that is, you want `a < b` to imply `a+c < b+c` for all `c` and `a`, but this is impossible). **Correction** : You can’t do it consistent with addition _and_ multiplication: you also want `0 < a` to imply `0 < a*a`. For arrays, there is no `*` operation, and lexicographical ordering is okay with `+` alone.

---

<div class="post-metadata">

**Author:** ![klacru](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/klacru/32/27890_2.png) [@klacru](https://discourse.julialang.org/u/klacru)\
**Post date:** [January 6, 2018, 12:16pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/15 "2018-01-06T12:16:32Z")

</div>

I think, that is a good example to explain how I understand “canonical”. Order relations are mathematical objects, which and they interrelate with other mathematical objects, like additive structures. There is a theory behind that, which works like a [mobile](https://en.wikipedia.org/wiki/Mobile_(sculpture)) in equilibrium - if you change one little part, it gets in motion and a lot of things do not work any more. That is why I am reluctant to extend the domain of certain functions, which handle mathematical objects to types, which do not behave “mathematically”.  
Let me come back to the original subject: how and if should `isless` and `cmp` be defined for `AbstractArray`?  
I would recommend, to keep the following contract valid:

For each a and b of the same type, which is in the domain of isless/cmp (ìsless(::T,::T) where T) exactly one of the following statements shall be true  
Either `isless(a,b) === true` or `isless(b,a) === true` or `isequal(a, b) === true`.  
Also `cmp(a,b) < 0 <=> isless(a,b)` and `cmp(a,b) > 0 <=> isless(b,a)` and `cmp(a,b) == 0 <=> isequal(a,b)`.

Besides that, of course associatitvity, antisymmetry, reflectivity has to be respected.

This contract can be followed by a lexicographical order for arrays, if you make the following restrictions:

1. Arrays of different shape cannot be compared (throw exception).
2. the elements are iterated in a defined fashion, which must be clear to the user, and compared element-wise until the first difference is detected.
3. The element type must follow the above contract about isless/cmp.

It is an open decision, if we restrict that to one-dimensional arrays (only one of the `size(a)` elements is different form `1`).

For `Tuple`, the decision to use lexicographical ordering has been made long ago and is ok. Tuples are in my reception less “mathematical” than arrays and vectors and serve different purposes.

For complex numbers, ordering would be surprising and on purpose. If there is a reason to present or process a set of complex numbers in a certain order, there are probably as many different orders as there are application uses. For example I once sorted eigenvalues first by abs of the real part, then by the negative of the imaginary part - and that was appropriate for my use case.  
I would prefer to not provide a standard ordering, but delegate that to the user. Reason

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [January 6, 2018, 2:08pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/16 "2018-01-06T14:08:34Z")

</div>

> [@jeff.bezanson](#):
>
> About that… \< has a fallback that calls isless; maybe we should remove it?

For most types, they are the same, and you’d have to define two comparison methods, which would be annoying. Maybe just define a `<` method for arrays that throws a method error?

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [January 6, 2018, 2:15pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/17 "2018-01-06T14:15:14Z")

</div>

> [@klacru](#):
>
> Order relations are mathematical objects, which and they interrelate with other mathematical objects, like additive structures.

~~Just to be clear, lexicographical ordering has _exactly_ the same problem for complex numbers and arrays in relation to `+`, due to the isomorphism between complex numbers and two-element arrays. That’s why it doesn’t make sense to me to define a lexicographical `isless` for one and not the other.~~

- _Correction_: Sorry, I wasn’t thinking clearly here. Lexicographical ordering is fine for `a<b ⟹ a+c<b+c`; the problem for complex numbers comes in the other requirement for an [ordered field](https://en.wikipedia.org/wiki/Ordered_field): you also want `0<a` to imply `0<a*a`, which is violated for lexicographical comparison with `a=im`. Arrays don’t have this problem because they don’t define `*`.

- So, this is a reasonable argument for defining lexicographical `isless` for arrays and not for complex numbers. But it is still true that `isless` already has fewer “algebraic” requirements than `<` in Julia…

On the other hand, since we have separate (non-synonymous) functions `isless` and `<`, only `<` seems like the “algebraic” one to me. `isless`, in contrast, is used purely for sorting and searching, and so I don’t think it needs to satisfy the algebraic properties that `<` does.

(For example, `isless` and `isequal` _already_ violate `isless(a,b) ⟹ isless(a+c,b+c)` for floating-point numbers. e.g. try `a=1`, `b=2`, `c=NaN`. `<` makes NaNs unordered, so it is in a different boat here. The use of the term “partial order” is still a bit funny for `<` because a strict partial order would probably throw an error for `NaN < NaN`.)

---

<div class="post-metadata">

**Author:** ![klacru](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/klacru/32/27890_2.png) [@klacru](https://discourse.julialang.org/u/klacru)\
**Post date:** [January 6, 2018, 2:18pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/18 "2018-01-06T14:18:06Z")

</div>

Defining `<(x::T,y:T) where T = isless(x,y)` is a good idea, in general, because if for a type `T` a canonical total order is defined, it is natural to use that also for `<`.  
In the other case, the contract for `<` is less restrictive than for `isless` in that it allows to implement partial orders. In the case of arrays (of same shape) that would be typically element-wise comparison. So

```julia
<(a::AbstractArray{T},b::AbstractArray{T}) where T = 
    begin size(a) != size(b) && error...; all(isless.(a, b)) end

```

would be useful. Kind regards.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [January 6, 2018, 2:21pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/19 "2018-01-06T14:21:15Z")

</div>

> [@klacru](#):
>
> `<` […] allows to implement implement partial orders. In the case of arrays (of same shape) that would be typically element-wise comparison

Element-wise comparison is not a [partial order](https://en.wikipedia.org/wiki/Partially_ordered_set). It isn’t an order at all. (It’s not a [binary relation](https://en.wikipedia.org/wiki/Binary_relation).)

Besides, we already have `.<` and `isless.` for element-wise comparison of arrays.

Maybe you meant `<(a,b) = all(isless.(a,b))`? I don’t think this would be terribly useful.

---

<div class="post-metadata">

**Author:** ![klacru](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/klacru/32/27890_2.png) [@klacru](https://discourse.julialang.org/u/klacru)\
**Post date:** [January 6, 2018, 2:59pm UTC](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176/20 "2018-01-06T14:59:11Z")

</div>

For me, `< ` also has an “algebraic” co-notation, because it is so frequently used for real numbers. Unfortunately the completion of ℝ with `NaN` is not a field any more. Arguments which use `NaN` are not mathematical. At the other hand `Float64` is also not exactly a field, and the mathematical branch of numerics has been handling the difference. The discussion about the differences between `<` and `isless` should be separated for the areas of `Real` (which does not contain `Complex` nor arrays) and other types.

For `Real` floats, the pair if `isless`/`isequal` models an absolute order including the special values `NaN` and `-0.0`, which is not the case for `<`/`==`.  
The pair of `<`/`==` are better suited for arithmetic operation, and they handle `-0.0` and `NaN` differently.

For other types, it has been defined to use `isless`/`isequal` for total orders and `==` to fall back to `isequal`. The `<` has a priory no meaning for those types. For convenience it has been defined to fall back to `isless`.  
For example for `Set` there is in general no useful total order, and `isless` is not defined. The natural order of sets is implemented by `issubset`.

My argument against giving a total order to `Complex` was because there no mathematically founded definition for such an order available (no mathematical theory about orders on complex numbers), and every order we define is as arbitrary and on purpose as the other.

…

[Next page](https://discourse.julialang.org/t/meaning-of-isless-cmp-isequal-total-order-partial-order-unordered/8176.md?page=2)