# 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:** 4

<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, 6:36pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/61 "2021-05-12T18:36:33Z")

</div>

> [@goretkin](#):
>
> We are lucky when outcomes of careful design for generic programming aligns with the expectations of every user, and we appear not to be lucky this time.

So I don’t don’t know if I’m in the minority here, but what happens if the design confounds the expectations of (say, for the sake of argument) 99% of users. What then?

Also, even after this long thread with many explanations, I am totally confused about what it means for something to be sorted. And I also have zero idea why the current design is better for generic programming. Or why ‘strict total ordering’ matters. Was this adressed?

I’m clearly being difficult, but I am curious, and I do have a math degree, and have sorted countless lists. How can this be explained to a ‘normal user’?

---

<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, 6:37pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/62 "2021-05-12T18:37:52Z")

</div>

> [@DNF](#):
>
> But what’s the relevance of that? The question I’m struggling with is “what does it mean for a sequence to be sorted according to some comparison operator?”

It sounds like you are willing to accept the claim that `isless` and `isequal` is more fundamental than `<=`. So, then your next struggle is also your solution: you must design a definition of “sequence is sorted” that relies on `isless`. You then notice (after a weird headache) that you can do it.

> This switching of order and negation causes weird results, and the motivation is opaque to me.

I find it wrong to say that that’s the reason for the weird results. Some people are getting weird results because they are guessing incorrectly at an implementation of a function. Not only is the guess incorrect, but so would be the implementation for the default value `isless`.

---

<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, 6:39pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/63 "2021-05-12T18:39:43Z")

</div>

> [@goretkin](#):
>
> It sounds like you are willing to accept the claim that `isless` and `isequal` is more fundamental than `<=` .

I don’t object to that. But why must sort be implemented in terms of the most fundamental function?

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [May 12, 2021, 6:40pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/64 "2021-05-12T18:40:00Z")

</div>

The definition Julia uses is that a list is sorted iff for every pair of elements, either:

1. The elements are equal
2. The first element is less than the second

The reason for this design is it only relies on users to define `==(a::T,b::T)` and `<(a::T,b::T)`.  
The reason to define `sort` in terms of the more fundamental function is to increase the chance that user defined methods will be used when applicable.

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [May 12, 2021, 6:41pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/65 "2021-05-12T18:41:15Z")

</div>

The design perfectly fits the expectation of users who know the mathematical definition of a total order, and that is much more than 1% of users.

---

<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, 6:42pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/66 "2021-05-12T18:42:30Z")

</div>

> [@Oscar\_Smith](#):
>
> - The elements are equal
> - The first element is less than the second

Then it would help a lot if the first clause was made very explicit. And that the `lt` input is subject to very strict requirements.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [May 12, 2021, 6:43pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/67 "2021-05-12T18:43:59Z")

</div>

Yeah. The docs probably should say something along the lines of “`lt` should be a function that forms a total order when combined with `isequal`”

---

<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, 6:44pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/68 "2021-05-12T18:44:45Z")

</div>

> [@Oscar\_Smith](#):
>
> The reason for this design is it only relies on users to define `==(a::T,b::T)` and `<(a::T,b::T)` .

That is not correct. All you need is `<` / `isless`. Take for example

```julia
julia> mutable struct Wrap
       _::Int
       end

julia> Base.isless(a::Wrap, b::Wrap) = isless(a._, b._)

julia> Wrap(3) == Wrap(3)
false

julia> issorted(map(Wrap, 1:10))
true

julia> issorted(map(Wrap, [1, 1, 1]))
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, 6:44pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/69 "2021-05-12T18:44:59Z")

</div>

> [@Jean\_Michel](#):
>
> and that is much more than 1% of users.

The number was for the sake of argument. But how big do you think that number is?

And as I said, the docs don’t even _mention_ “total order” (or do they), so why would I expect that to be relevant?

---

<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, 6:48pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/70 "2021-05-12T18:48:32Z")

</div>

> [@DNF](#):
>
> And as I said, the docs don’t even _mention_ “total order” (or do they), so why would I expect that to be relevant?

The documentation for `Base.isless` does mention “total order” ([Understanding issorted's lt keyword - #2 by goretkin](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/2)) . And `isless` is the default argument. The connection isn’t as clear as could be, but it’s there.

---

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

</div>

The default argument creates(?) a total ordering, but it doesn’t follow that all arguments must do so.

Oh, well, it’s getting late. Maybe sleeping on it will help.

---

<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, 8:26pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/72 "2021-05-12T20:26:27Z")

</div>

> [@goretkin](#):
>
> It sounds like you are willing to accept the claim that `isless` and `isequal` is more fundamental than `<=` .

I don’t see a ranking of fundamentalness between \< and \<=. It’s possible to define either in terms of the other. A [total order](https://en.wikipedia.org/wiki/Total_order) is normally defined in terms of \<=.

Checking the strict-sortedness of a collection that allows duplicates seems like a type error. `isstrictlysorted(x::OrderedSet)` is fine but `isstrictlysorted(x::Vector)` doesn’t make much sense, or at least is error prone.

---

<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, 8:47pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/73 "2021-05-12T20:47:15Z")

</div>

> [@sostock](#):
>
> > [@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.

My contention is that `issorted` already contains that loop. What I’m not sure about is if I would be I’m exploiting documented behavior or an implementation detail by using `issorted( ..., lt = <=)`.

---

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

</div>

> [@jzr](#):
>
> I don’t see a ranking of fundamentalness between \< and \<=. It’s possible to define either in terms of the other.

Yes, both choices are possible. And a choice has already been made. This allows `Base` to have fallback methods.

Can you explain what you don’t see here in the [previous post](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/55)? You can also just look at the docstrings for `isless`, `<`, `<=`, etc.

To be precise, my claim was about `isless` and `<=`, not `<` and `<=`. And to be less precise, I did use scare quotes around _fundamental_. I would not say one of these concepts are inherently more fundamental than the other, but a choice has been made to define (by default) comparisons in terms of `isless`, and not e.g. to define `isless` in terms of `<=`.

A user is able to make another choice for their own type. They could define `<=` first, and then define `isless` in terms of `<=` and `==`. Their method definition for `isless` will look generic, but because the user has gone against the design intention of the generic functions, these methods must be limited to their own type, otherwise there will be method ambiguities.

I am really struggling to understand the confusion here. Some people are wishing that `issorted` was defined in terms of something like `<=`. Okay, but it’s not. That it is defined in terms of something like `isless` is reasonable.

---

<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:04pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/75 "2021-05-12T22:04:28Z")

</div>

> [@goretkin](#):
>
> That it is defined in terms of something like `isless` is reasonable.

I don’t think running `isstrictlysorted(::ArrayWithDuplicates)` is usually the user’s intent when they run `issorted(lst)`, and having [footguns](https://en.wiktionary.org/wiki/footgun) lying around is a bad property in a language.

> [@goretkin](#):
>
> I am really struggling to understand the confusion here. Some people are wishing that `issorted` was defined in terms of something like `<=` . Okay, but it’s not.

I’m arguing we should change it. Several ideas arise.

1. Rename `issorted` to `isstrictlysorted` and introduce `isweaklysorted` which behaves in the expected way
2. Error on collections that contain duplicates.
3. Error on duplicate-allowing collection types. E.g. error on `Vector`, allow for `OrderedSet`.

I prefer not to error (2,3) because it reduces genericness. Having explicit function names (1) is better.

(Sorry about all the edits.)

---

<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, 10:21pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/76 "2021-05-12T22:21:23Z")

</div>

> [@jzr](#):
>
> I don’t think running `isstrictlysorted(::ArrayWithDuplicates)` is reasonable

First of all, what does this mean? Secondly, just because the answer to something is `false`, doesn’t mean it’s unreasonable to ask the question.

Please show an actual piece of code that you think is a footgun.

I am going to guess that it’s this:

```julia
julia> issorted([1, 1], lt = <=)
false

```

And the footgun is that a user expects that it returns `true`? The user will have to have read the docstring for `issorted` to even know the keyword argument is called `lt`:

> 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.

So, after reading that, the user passes in `lt = <=`. What is the logical or emotional justification for a user doing that?

---

<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:21pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/77 "2021-05-12T22:21:48Z")

</div>

Yeah I deleted that line 🙂

---

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

</div>

> [@jzr](#):
>
> I don’t think running `isstrictlysorted(::ArrayWithDuplicates)` is usually the user’s intent when they run `issorted(lst)`

This edit still doesn’t help me understand what you meant.

Current behavior:

```julia
julia> issorted([1, 1])
true

```

it’s not a test of whether the list (which, by the way, contains duplicates) is “strictly sorted”.

---

<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:27pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/79 "2021-05-12T22:27:11Z")

</div>

Sorry for the confusion, I wrote inaccurately above. The unexpected behavior is

```julia
julia> issorted([1,1], lt=<=)
false

```

and more generally that `issorted(sort(seq, lt=f), lt=f)` isn’t necessarily `true` for collections with duplicates.

Maybe a solution is to provide an `le=` parameter.

---

<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, 10:41pm UTC](https://discourse.julialang.org/t/understanding-issorteds-lt-keyword/60918/80 "2021-05-12T22:41:15Z")

</div>

> [@jzr](#):
>
> `issorted(sort(seq, lt=f), lt=f)` isn’t necessarily `true` for collections with duplicates.

It is true if you pass in appropriate choices for `f`. The solution is to document appropriate choices directly. Right now it’s quite indirectly documented in `sort!`:

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

So the footgun, aside from the indirect documentation, is that `<=` seems like a reasonable choice for a “less than” function to you. So a solution would be to add e.g.:

> Note, `<=` is not a “less than” function.

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

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