# 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:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![ettersi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ettersi/32/6829_2.png) [@ettersi](https://discourse.julialang.org/u/ettersi)\
**Post date:** [May 12, 2021, 7:35am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/21 "2021-05-12T07:35:57Z")

</div>

I don’t see where the documentation specifies how `issorted` should treat equal elements. My guess is that the authors of `issorted()` assumed `lt` to be a strict comparison (i.e. `lt(a,a) == false`) but failed to document this. `lt = <=` is then simply an invalid input.

---

<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, 7:44am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/22 "2021-05-12T07:44:35Z")

</div>

> [@sostock](#):
>
> On one hand, you expect that `issorted(sort(A, lt=x), lt=x)` returns `true` for all `x` (which is the case if `x` defines a strict total order).

I think that’s what I want. Uniqueness seems unrelated to sortedness.

> [@sostock](#):
>
> - On the other hand, you want to have a `my_lt` (either `<` or `<=` ) such that `issorted(sort(A, lt=my_lt))` returns `false` when `A` contains non-unique elements.

Why would I want that?

> [@sostock](#):
>
> We should definitely document that `lt` must define a [strict total order](https://en.wikipedia.org/wiki/Total_order#Strict_and_non-strict_total_orders)

I don’t think we should change the documentation; instead we should change the behavior to conform to the documentation.

---

<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, 7:48am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/23 "2021-05-12T07:48:34Z")

</div>

> [@ettersi](#):
>
> I don’t see where the documentation specifies how `issorted` should treat equal elements.

The documentation says

> Test whether a vector is in sorted order. The lt, by and rev keywords modify what order is considered to be sorted just as they do for sort.

IMO the most obvious reading of “just as they do for `sort`” – and the most obvious behavior irrespective of documentation – is that `issorted(sort(seq, lt=f), lt=f)` is true.

---

<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 12, 2021, 7:51am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/24 "2021-05-12T07:51:05Z")

</div>

> [@jzr](#):
>
> > [@sostock](#):
> >
> > - On the other hand, you want to have a `my_lt` (either `<` or `<=` ) such that `issorted(sort(A, lt=my_lt))` returns `false` when `A` contains non-unique elements.
> 
> Why would I want that?

Sorry, I didn’t mean to imply that that’s what you want, it is the motivation of the OP:

> [@mkitti](#):
>
> Part of the reason I am interested in `lt = <=` is that I actually want to verify that an iterable is both sorted and unique. I want the sequence to be strictly monotonically increasing, not just sorted.
> 
> My intuition would have been to indicate `lt = <` to accomplish that, but that is wrong.

---

<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, 7:52am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/25 "2021-05-12T07:52:50Z")

</div>

> [@sostock](#):
>
> it is the motivation of the OP

Aha, for that case, I would use `sort ∘ unique` to change the sequence, and `allunique(seq) && issorted(seq)` to check.

---

<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 12, 2021, 7:58am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/26 "2021-05-12T07:58:40Z")

</div>

> [@jzr](#):
>
> I don’t think we should change the documentation; instead we should change the behavior to conform to the documentation.

I don’t see where the current behavior contradicts the documentation. The documentation is just vague. It doesn’t tell you whether `lt` should implement a _total order_ or a _strict total order_, although it uses `isless` as a default, which implements a strict total order.

---

<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 12, 2021, 9:21am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/27 "2021-05-12T09:21:02Z")

</div>

> [@sostock](#):
>
> So what should `sort(A, lt=my_lt)` do?

If `A` has non-unique elements, I guess `sort(A; lt=<=)` should work, and `sort(A; lt=<)` should throw an error. I _think_.

Furthermore, if `A` has non-unique elements `issorted(A; lt=<)` should return (after sorting) `false`, and `issorted(A; lt=<=)` should return `true`.

---

<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 12, 2021, 9:35am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/28 "2021-05-12T09:35:35Z")

</div>

> [@sostock](#):
>
> I don’t see where the current behavior contradicts the documentation. The documentation is just vague.

I agree. It’s just that the behaviour is extremely counter-intuitive. To some, at least. Do you find the current behaviour intuitive? As in, if you just read the docstring for the first time, this is what you would expect:

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

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

```

?

If this is reasonably obvious to many users, then I guess this comes down to habit, I just thought the obvious behaviour was

```julia
issorted([a, b]; lt=foo) <==> foo(a, b)

```

---

<div class="post-metadata">

**Author:** ![carstenbauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carstenbauer/32/4981_2.png) [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)\
**Post date:** [May 12, 2021, 9:38am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/29 "2021-05-12T09:38:56Z")

</div>

Personally, I would have never provided `<=` as `lt`. After all it stands for “less than” and not “less than or equal”. So, for me, the strict order constraint, although not explicitly mentioned, coincides with my intuition.

(I would be fine with expanding the documentation in this regard or changing the implementation without modifying the behaviour for strict order comparisons.)

---

<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 12, 2021, 9:46am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/30 "2021-05-12T09:46:58Z")

</div>

> [@carstenbauer](#):
>
> Personally, I would have never provided `<=` as `lt` . After all it stands for “less than” and not “less than or equal”.

I’m struggling to understand this argument. It seems to argue about what sort of comparisons one _ought to_ input, not how the comparison should be used.

You can provide whatever binary function you want, not sure why the abbreviation should dictate that. `<=` is accepted. The way I read it is

> `lt=foo` : `a` is considered less than `b` if `foo(a, b)` is true.

You could use `lt=(>)` if you like, or even `lt=(x,y)->rand(Bool)`.

---

<div class="post-metadata">

**Author:** ![mkitti](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mkitti/32/12459_2.png) [@mkitti](https://discourse.julialang.org/u/mkitti)\
**Post date:** [May 12, 2021, 9:57am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/31 "2021-05-12T09:57:24Z")

</div>

> [@jzr](#):
>
> Aha, for that case, I would use `sort ∘ unique` to change the sequence, and `allunique(seq) && issorted(seq)` to check.

Are `sort ∘ unique` and `allunique(seq) && issorted(seq)` really the most efficient way to accomplish those tasks?

For the former, perhaps `sorted_unique(x) = (unique! ∘ sort! ∘ copy)(x)`

---

<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 12, 2021, 10:46am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/32 "2021-05-12T10:46:11Z")

</div>

> [@DNF](#):
>
> You could use `lt=(>)` if you like, or even `lt=(x,y)->rand(Bool)` .

That is a very good example. Yes, you _can_ input any binary function that returns a `Bool`. But if you would actually use `lt=(x,y)->rand(Bool)`, would you consider the result useful?

If yes, do you think the current implementation of `sort`/`issorted` is at fault for making this `lt` not work in a useful way?

If no, then why do you think the result for `lt=<=` would be useful?

---

<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 12, 2021, 10:47am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/33 "2021-05-12T10:47:16Z")

</div>

> [@mkitti](#):
>
> Are `sort ∘ unique` and `allunique(seq) && issorted(seq)` really the most efficient way to accomplish those tasks?

No, the most efficient would probably be a loop.

---

<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 12, 2021, 10:53am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/34 "2021-05-12T10:53:03Z")

</div>

> [@sostock](#):
>
> would you consider the result useful?

If you want a random shuffle, why not? Useful is in the eye of the beholder.

> [@sostock](#):
>
> If no, then why do you think the result for `lt=<=` would be useful?

Not sure I understand the question. It would be useful because every pair of elements would satisfy that comparison, every element would be ‘less than or equal to’ the next element.

On the other hand, `lt=<` would mean that every element is strictly smaller than the next. But that’s not the current behavior.

---

<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 12, 2021, 10:55am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/35 "2021-05-12T10:55:24Z")

</div>

Okay. So let’s assume you did `sort(A, lt=(x,y)->rand(Bool))`. You now expect `A` to be sorted according to `lt`, so `issorted(A, lt=(x,y)->rand(Bool))` should return `true`. You try it and it returns `false`! Do you consider that a bug in `sort`/`issorted`?

---

<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 12, 2021, 10:56am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/36 "2021-05-12T10:56:48Z")

</div>

No, this is a reasonable exception, occurring because I input a ‘perverse’ comparison function.

I can do `shuffle!(A)` but testing for ‘shuffleness’ wouldn’t make sense.

---

<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 12, 2021, 10:58am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/37 "2021-05-12T10:58:42Z")

</div>

But `<=` is a ‘perverse’ comparison function as well, because it does not implement a strict total order.

---

<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 12, 2021, 10:59am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/38 "2021-05-12T10:59:27Z")

</div>

Why would I care about that. It implements a reasonable comparison.

“Each element is less than or equal to the next” is a perfectly fine way of sorting, and is in fact what `sort(A)` returns.

---

<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 12, 2021, 11:07am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/39 "2021-05-12T11:07:58Z")

</div>

> [@DNF](#):
>
> Why would I care about that. It implements a reasonable comparison.

How do you define “reasonable comparison”? For me, in the context of `sort`/`issorted` a reasonable comparison is defined by a strict total order.

> [@DNF](#):
>
> “Each element is less than or equal to the next” is a perfectly fine way of sorting, and is in fact what `sort(A)` returns.

If `sort` explicitly wants a “lesser than” function, a “lesser than or equal” function does not seem perfectly fine to me. How would Julia figure out whether you supplied a strict total order or a non-strict total order?

---

<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 12, 2021, 11:18am UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/40 "2021-05-12T11:18:48Z")

</div>

> [@sostock](#):
>
> How do you define “reasonable comparison”?

I don’t. Whatever works is fine. Including random. It’s just that you cannot expect random sorts to be repeatable.

> [@sostock](#):
>
> For me, in the context of `sort` / `issorted` a reasonable comparison is defined by a strict total order.

But then how can you do sorting of non-unique vectors? Every element will not be strictly less than the next, therefore not sorted.

> [@sostock](#):
>
> If `sort` explicitly wants a “lesser than” function

Where is this made explicit? The closest I could find was

> the `lt` keyword allows providing a custom “less than” function

in the manual, and nothing in the docstring.

> [@sostock](#):
>
> a “lesser than or equal” function does not seem perfectly fine to me.

But it does actually accept “lesser than or equal”, since `issorted([1,2,2,3])` is `true`, and that is only sorted if equal is accepted as “less than”.

> [@sostock](#):
>
> How would Julia figure out whether you supplied a strict total order or a non-strict total order?

Why should it figure that out?

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

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