# Understanding issorted's lt keyword

**URL:** <https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918>\
**Category:** New to Julia\
**Created:** [May 10, 2021, 9:34pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918 "2021-05-10T21:34:36Z")\
**Posts on this page:** 9\
**Page:** 5

<div class="post-metadata">

**Author:** ![jzr](https://avatars.discourse-cdn.com/v4/letter/j/eb9ed0/32.png) [@jzr](https://discourse.julialang.org/u/jzr)\
**Post date:** [May 12, 2021, 10:52pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/81 "2021-05-12T22:52:24Z")

</div>

> [@goretkin](#):
>
> So the footgun, aside from the indirect documentation and lack of explicit counter examples is that `<=` seems like a reasonable choice for a “less than” function to you.

Yeah, basically.

In other words, the issue is that it’s asking for a function that has certain properties when that isn’t what I expect it to be asking for, and it gives undesirable results when I give it something that I naively think is similar.

Putting a warning message on it may help sometimes, but designing the API so that it doesn’t need a warning message since it already conforms to expectations may be more successful.

---

<div class="post-metadata">

**Author:** ![goretkin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goretkin/32/167_2.png) [@goretkin](https://discourse.julialang.org/u/goretkin)\
**Post date:** [May 12, 2021, 11:01pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/82 "2021-05-12T23:01:04Z")

</div>

> [@jzr](#):
>
> Putting a warning message on it may help sometimes, but designing the API so that it doesn’t need a warning message since it already conforms to expectations may be more successful.

I think it’s obvious that it is not possible to design an API that conforms to everyone’s expectations, though it is a worthy ideal to keep in mind. But there are other important ideals, such as consistency, and enabling generic programming. Julia Base has broken the “tie” between “define `<=` in terms of `<` or vice versa?”. The definition of `issorted` follows as a consequence, consistently.

You do not appear to be considering all of the other implications of changing the chosen design. Since you are not the OP, it also seems that you have not run into this problem yourself.

If you haven’t already, please read [PSA: Julia is not at that stage of development anymore](https://discourse.julialang.org/t/psa-julia-is-not-at-that-stage-of-development-anymore/44872) .

---

<div class="post-metadata">

**Author:** ![jzr](https://avatars.discourse-cdn.com/v4/letter/j/eb9ed0/32.png) [@jzr](https://discourse.julialang.org/u/jzr)\
**Post date:** [May 12, 2021, 11:15pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/83 "2021-05-12T23:15:43Z")

</div>

> [@goretkin](#):
>
> You do not appear to be considering all of the other implications of changing the chosen design.

I guess that’s true.

> [@goretkin](#):
>
> Julia Base has broken the “tie” between “define `<=` in terms of `<` or vice versa?”. The definition of `issorted` follows as a consequence, consistently.

Could you spell out why this follows?

---

<div class="post-metadata">

**Author:** ![FPGro](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fpgro/32/20822_2.png) [@FPGro](https://discourse.julialang.org/u/FPGro)\
**Post date:** [May 12, 2021, 11:37pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/84 "2021-05-12T23:37:25Z")

</div>

I’ve just dug out all the history of the `issorted` function (which is surprisingly hard) and came to the conclusion that it’s fine. What transpired is, that at no point in this whole thing, using `<=` as an ordering inducing function was considered to be meaningful.

When the (precursor) of the current implementation `lt(this, prev)` (not literally) was introduced, sorting orders were actually determined by a pair of `lt, le` functions, but the second part was dropped, probably because it is somewhat redundant when one sticks to the requirements of “less than” for inducing order. It’s clear that there is no “less equallier” function belonging to `<=` like `<=` belongs to `<`.

Fast forward: how order is defined is actually documented by `isless`, much more clearly than what `sort` has to say about the `lt` keyword. The critical part is that the `lt` keyword gets tranformed to a `Base.Lt`, which is actually pretty clear about what you can meaningfully do with it:

```julia
help?> Base.Lt
  Lt(lt)

  Ordering which calls lt(a, b) to compare elements. lt should obey the same rules as implementations of isless.

```

So we should probably just make `issorted` and `sort` point to `Base.Lt` (or `isless` directly) for the explanation of the `lt` keyword and consider it done.

The fact that using `lt = <=` actually yields an equivalent of `issorted && allunique` is a peculiar implementation detail but not more then. (Answering the initial question) Exploiting this is probably still relying on an implementation detail but one that is unlikely to change anytime soon.

---

<div class="post-metadata">

**Author:** ![gustaphe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gustaphe/32/18174_2.png) [@gustaphe](https://discourse.julialang.org/u/gustaphe)\
**Post date:** [May 13, 2021, 4:51am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/85 "2021-05-13T04:51:07Z")

</div>

To get the desired behaviour:

```julia
using IterTools.partition
isinorder(x; order=<=) = all(t->order(t...), partition(x, 2, 1))

isinorder([1, 1, 2]) == true
isinorder([2, 1, 1]) == false
isinorder([1, 1, 2]; order=<) == false
isinorder ([1, 1, 2]; order=x->true) == true

```

---

<div class="post-metadata">

**Author:** ![goretkin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goretkin/32/167_2.png) [@goretkin](https://discourse.julialang.org/u/goretkin)\
**Post date:** [May 13, 2021, 5:13am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/86 "2021-05-13T05:13:04Z")

</div>

This is in essence what I wrote 80 posts ago: [Understanding issorted's lt keyword - #7 by goretkin](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/7) 🙃

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [May 13, 2021, 10:18am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/87 "2021-05-13T10:18:06Z")

</div>

I’m fine with this being better documented, and not changed.

But I must say I am a bit baffled that it’s apparently so hard to see why the current behaviour is surprising. Understanding the current behaviour requires an _extremely_ high level of mathematical sophistication. If you are capable of that then it makes sense (I presume, I’m only a Msc in mathematics, I don’t think this is within my intellectual reach), and I don’t mind that Julia normally chooses ‘correctness’ over intuition.

But after this many posts, it’s really strange that there is apparently zero understanding among some, such as @goretkin, that this

```julia
jl> issorted([1,2,2,3]; lt=<=)
false

jl> issorted([1,2,2,3]; lt=<)
true

```

is surprising and weird for people below the PhD level. It may be correct, but it is _strange_.

What all of this has to do with which is more ‘fundamental’ of `isless` or `<` is, unfortunately, also beyond me. It’s fine that `isless` is the default, because it’s more fundamental, but that _alone_ doesn’t explain why `<=` cannot also be used.

---

<div class="post-metadata">

**Author:** ![sostock](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sostock/32/5546_2.png) [@sostock](https://discourse.julialang.org/u/sostock)\
**Post date:** [May 14, 2021, 12:15pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/88 "2021-05-14T12:15:59Z")

</div>

> [@mkitti](#):
>
> What I’m not sure about is if I would be I’m exploiting documented behavior or an implementation detail by using `issorted( ..., lt = <=)` .

I would say it is an implementation detail that `issorted(A, lt=<=)` behaves as `issorted(A) && allunique(A)`. It is definitely not documented behavior. It also doesn’t work if `NaN`s are involved:

```julia
julia> issorted([2, NaN, 1], lt=<=)
true

```

(`NaN` is not ordered with `<` and `<=`, which means that `x < NaN`, `x <= NaN`, `NaN < x` and `NaN <= x` return `false` for every `x`. That’s why `lt=isless` is the default, not `lt=<`.)

You can certainly use it (if you know that you don’t have to deal with `NaN` or have to distinguish between `-0.0` and `0.0`), but it might be more clear to write your own function for this. You could just copy the implementation of `issorted` and adapt it to your case.

---

<div class="post-metadata">

**Author:** ![sostock](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sostock/32/5546_2.png) [@sostock](https://discourse.julialang.org/u/sostock)\
**Post date:** [May 14, 2021, 12:23pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/89 "2021-05-14T12:23:52Z")

</div>

What about adding something like the following to the `sort!` docstring:

> If a custom `lt` function is supplied, it should behave like a “less than” function (as opposed to a “less than or equal” function), i.e., for every `x` and `y`, only one of `lt(x,y)` and `lt(y,x)` can return `true`.

[Previous page](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918.md?page=4)