sorted?

sorted?

[Jeremy Korwin-Zmijowski]

Hi Guilers,


Doing Advent of Code 2024, I was trying to use `sorted?` procedure. And 
something bothered me.

The reference says :

    Scheme Procedure: *sorted?* items less
    C Function: *scm_sorted_p* (items, less)

        Return |#t| if items is a list or vector such that, for each
        element x and the next element y of items, |(less y x)| returns
        |#f|. Otherwise return |#f|.

I think the description should be :

    Return |#t| if items is a list or vector such that, for each element
    x and the next element y of items, |(less y x)| returns |#t|.
    Otherwise return |#f|.

Then, testing it in the REPL give me this :

scheme@(guile-user)> (sorted? '(1 2 3) <)
$13 = #t

So far so good.

scheme@(guile-user)> (sorted? '(3 2 1) <)
$16 = #f

Still good. But

scheme@(guile-user)> (sorted? '(1 1) <)
$17 = #t

I was expecting #f due to

scheme@(guile-user)> (< 1 1)
$18 = #f


Anything I missed on the way maybe…

Jérémy

Re: sorted?

[Ricardo G. Herdt]

Hi Jeremy,

Am 09.12.2024 11:21 schrieb Jeremy Korwin-Zmijowski:
> The reference says :
> 
>    Scheme Procedure: *sorted?* items less
>    C Function: *scm_sorted_p* (items, less)
> 
>        Return |#t| if items is a list or vector such that, for each
>        element x and the next element y of items, |(less y x)| returns
>        |#f|. Otherwise return |#f|.
> 
> I think the description should be :
> 
>    Return |#t| if items is a list or vector such that, for each element
>    x and the next element y of items, |(less y x)| returns |#t|.
>    Otherwise return |#f|.

Actually no, since less is applied to y and x in that order. This way 
(sorted? '(1 1) <) correctly returns #t as your experiments show.

Regards,

Ricardo

Re: sorted?

[tomas]

[-- Attachment #1: Type: text/plain, Size: 979 bytes --]

On Mon, Dec 09, 2024 at 11:37:33AM +0000, Ricardo G. Herdt wrote:
> Hi Jeremy,
> 
> Am 09.12.2024 11:21 schrieb Jeremy Korwin-Zmijowski:
> > The reference says :
> > 
> >    Scheme Procedure: *sorted?* items less
> >    C Function: *scm_sorted_p* (items, less)
> > 
> >        Return |#t| if items is a list or vector such that, for each
> >        element x and the next element y of items, |(less y x)| returns
> >        |#f|. Otherwise return |#f|.
> > 
> > I think the description should be :
> > 
> >    Return |#t| if items is a list or vector such that, for each element
> >    x and the next element y of items, |(less y x)| returns |#t|.
> >    Otherwise return |#f|.
> 
> Actually no, since less is applied to y and x in that order. This way
> (sorted? '(1 1) <) correctly returns #t as your experiments show.

I don't get it. (< 1 1) is /always/ #f, regardless of the order of the
ones?

I'm as confused as Jeremy is.

Cheers
-- 
tomás

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: sorted?

[Mikael Djurfeldt]

On Mon, Dec 9, 2024 at 12:43 PM <tomas@tuxteam.de> wrote:

> On Mon, Dec 09, 2024 at 11:37:33AM +0000, Ricardo G. Herdt wrote:
> > Hi Jeremy,
> >
> > Am 09.12.2024 11:21 schrieb Jeremy Korwin-Zmijowski:
> > > The reference says :
> > >
> > >    Scheme Procedure: *sorted?* items less
> > >    C Function: *scm_sorted_p* (items, less)
> > >
> > >        Return |#t| if items is a list or vector such that, for each
> > >        element x and the next element y of items, |(less y x)| returns
> > >        |#f|. Otherwise return |#f|.
> > >
> > > I think the description should be :
> > >
> > >    Return |#t| if items is a list or vector such that, for each element
> > >    x and the next element y of items, |(less y x)| returns |#t|.
> > >    Otherwise return |#f|.
> >
> > Actually no, since less is applied to y and x in that order. This way
> > (sorted? '(1 1) <) correctly returns #t as your experiments show.
>
> I don't get it. (< 1 1) is /always/ #f, regardless of the order of the
> ones?
>
> I'm as confused as Jeremy is.
>

sorted? checks whether *a list* has its elements sorted. It does not apply
a predicate to all successive pairs like some fold operation. Two
consecutive equal elements are in sorted order since it wouldn't matter if
you switched them. The less operation is used to sort the list (or check
it).

Re: sorted?

[tomas]

[-- Attachment #1: Type: text/plain, Size: 1675 bytes --]

On Mon, Dec 09, 2024 at 01:20:48PM +0100, Mikael Djurfeldt wrote:
> On Mon, Dec 9, 2024 at 12:43 PM <tomas@tuxteam.de> wrote:
> 
> > On Mon, Dec 09, 2024 at 11:37:33AM +0000, Ricardo G. Herdt wrote:
> > > Hi Jeremy,
> > >
> > > Am 09.12.2024 11:21 schrieb Jeremy Korwin-Zmijowski:
> > > > The reference says :
> > > >
> > > >    Scheme Procedure: *sorted?* items less
> > > >    C Function: *scm_sorted_p* (items, less)
> > > >
> > > >        Return |#t| if items is a list or vector such that, for each
> > > >        element x and the next element y of items, |(less y x)| returns
> > > >        |#f|. Otherwise return |#f|.
> > > >
> > > > I think the description should be :
> > > >
> > > >    Return |#t| if items is a list or vector such that, for each element
> > > >    x and the next element y of items, |(less y x)| returns |#t|.
> > > >    Otherwise return |#f|.
> > >
> > > Actually no, since less is applied to y and x in that order. This way
> > > (sorted? '(1 1) <) correctly returns #t as your experiments show.
> >
> > I don't get it. (< 1 1) is /always/ #f, regardless of the order of the
> > ones?
> >
> > I'm as confused as Jeremy is.
> >
> 
> sorted? checks whether *a list* has its elements sorted. It does not apply
> a predicate to all successive pairs like some fold operation. Two
> consecutive equal elements are in sorted order since it wouldn't matter if
> you switched them. The less operation is used to sort the list (or check
> it).

Thanks for your explanation. I must admit that I'm still confused. Perhaps
I'll have to have a look at the implementation.

I'm sometimes slow :-)

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: sorted?

[Mikael Djurfeldt]

On Mon, Dec 9, 2024 at 1:37 PM <tomas@tuxteam.de> wrote:

> On Mon, Dec 09, 2024 at 01:20:48PM +0100, Mikael Djurfeldt wrote:
> > On Mon, Dec 9, 2024 at 12:43 PM <tomas@tuxteam.de> wrote:
> >
> > > On Mon, Dec 09, 2024 at 11:37:33AM +0000, Ricardo G. Herdt wrote:
> > > > Hi Jeremy,
> > > >
> > > > Am 09.12.2024 11:21 schrieb Jeremy Korwin-Zmijowski:
> > > > > The reference says :
> > > > >
> > > > >    Scheme Procedure: *sorted?* items less
> > > > >    C Function: *scm_sorted_p* (items, less)
> > > > >
> > > > >        Return |#t| if items is a list or vector such that, for each
> > > > >        element x and the next element y of items, |(less y x)|
> returns
> > > > >        |#f|. Otherwise return |#f|.
> > > > >
> > > > > I think the description should be :
> > > > >
> > > > >    Return |#t| if items is a list or vector such that, for each
> element
> > > > >    x and the next element y of items, |(less y x)| returns |#t|.
> > > > >    Otherwise return |#f|.
> > > >
> > > > Actually no, since less is applied to y and x in that order. This way
> > > > (sorted? '(1 1) <) correctly returns #t as your experiments show.
> > >
> > > I don't get it. (< 1 1) is /always/ #f, regardless of the order of the
> > > ones?
> > >
> > > I'm as confused as Jeremy is.
> > >
> >
> > sorted? checks whether *a list* has its elements sorted. It does not
> apply
> > a predicate to all successive pairs like some fold operation. Two
> > consecutive equal elements are in sorted order since it wouldn't matter
> if
> > you switched them. The less operation is used to sort the list (or check
> > it).
>
> Thanks for your explanation. I must admit that I'm still confused. Perhaps
> I'll have to have a look at the implementation.
>
> I'm sometimes slow :-)
>

No problem---I'm too.

Think about it this way:

How would you sort this list of numbers: 7 1 3 8 2 1 4 ?

It's 1 1 2 3 4 7 8, right? That is what we want (sort '(7 1 3 8 2 1 4)) to
output (+ the parentheses of course).

Now, `sorted?' returns true if its input is what `sort' would have produced
as output, otherwise false.

Re: sorted?

[Mikael Djurfeldt]

On Mon, Dec 9, 2024 at 1:58 PM Mikael Djurfeldt <mikael@djurfeldt.com>
wrote:

> On Mon, Dec 9, 2024 at 1:37 PM <tomas@tuxteam.de> wrote:
>
>> On Mon, Dec 09, 2024 at 01:20:48PM +0100, Mikael Djurfeldt wrote:
>> > On Mon, Dec 9, 2024 at 12:43 PM <tomas@tuxteam.de> wrote:
>> >
>> > > On Mon, Dec 09, 2024 at 11:37:33AM +0000, Ricardo G. Herdt wrote:
>> > > > Hi Jeremy,
>> > > >
>> > > > Am 09.12.2024 11:21 schrieb Jeremy Korwin-Zmijowski:
>> > > > > The reference says :
>> > > > >
>> > > > >    Scheme Procedure: *sorted?* items less
>> > > > >    C Function: *scm_sorted_p* (items, less)
>> > > > >
>> > > > >        Return |#t| if items is a list or vector such that, for
>> each
>> > > > >        element x and the next element y of items, |(less y x)|
>> returns
>> > > > >        |#f|. Otherwise return |#f|.
>> > > > >
>> > > > > I think the description should be :
>> > > > >
>> > > > >    Return |#t| if items is a list or vector such that, for each
>> element
>> > > > >    x and the next element y of items, |(less y x)| returns |#t|.
>> > > > >    Otherwise return |#f|.
>> > > >
>> > > > Actually no, since less is applied to y and x in that order. This
>> way
>> > > > (sorted? '(1 1) <) correctly returns #t as your experiments show.
>> > >
>> > > I don't get it. (< 1 1) is /always/ #f, regardless of the order of the
>> > > ones?
>> > >
>> > > I'm as confused as Jeremy is.
>> > >
>> >
>> > sorted? checks whether *a list* has its elements sorted. It does not
>> apply
>> > a predicate to all successive pairs like some fold operation. Two
>> > consecutive equal elements are in sorted order since it wouldn't matter
>> if
>> > you switched them. The less operation is used to sort the list (or check
>> > it).
>>
>> Thanks for your explanation. I must admit that I'm still confused. Perhaps
>> I'll have to have a look at the implementation.
>>
>> I'm sometimes slow :-)
>>
>
> No problem---I'm too.
>
> Think about it this way:
>
> How would you sort this list of numbers: 7 1 3 8 2 1 4 ?
>
> It's 1 1 2 3 4 7 8, right? That is what we want (sort '(7 1 3 8 2 1 4)) to
> output (+ the parentheses of course).
>
> Now, `sorted?' returns true if its input is what `sort' would have
> produced as output, otherwise false.
>
> Don't confused by the "less" that you pass in as second argument to
`sort'. That is something you are *required* to pass to sort for it to
function as expected. It is something that `sort' uses.

Re: sorted?

[Jeremy Korwin-Zmijowski]

>> No problem---I'm too.
>>
>> Think about it this way:
>>
>> How would you sort this list of numbers: 7 1 3 8 2 1 4 ?
>>
>> It's 1 1 2 3 4 7 8, right? That is what we want (sort '(7 1 3 8 2 1 4)) to
>> output (+ the parentheses of course).
>>
>> Now, `sorted?' returns true if its input is what `sort' would have
>> produced as output, otherwise false.
>>
>> Don't confused by the "less" that you pass in as second argument to
> `sort'. That is something you are *required* to pass to sort for it to
> function as expected. It is something that `sort' uses.

This explanation does make sense to me and so made me realized I was not 
using `sorted?` as it is intended to. I will think about another strategy.

Thank you all for your time and words.

Jérémy

Re: sorted?

[tomas]

[-- Attachment #1: Type: text/plain, Size: 748 bytes --]

On Mon, Dec 09, 2024 at 01:58:08PM +0100, Mikael Djurfeldt wrote:

[...]

> No problem---I'm too.
> 
> Think about it this way:
> 
> How would you sort this list of numbers: 7 1 3 8 2 1 4 ?
> 
> It's 1 1 2 3 4 7 8, right? That is what we want (sort '(7 1 3 8 2 1 4)) to
> output (+ the parentheses of course).
> 
> Now, `sorted?' returns true if its input is what `sort' would have produced
> as output, otherwise false.

Hmmm. Perhaps, what throws me off the rails is that you can pass
a "less" predicate to sorted?.

To behave like it does, it has to have some notion of equality,
which seems to be implicit and doesn't necessarily harmonize with
the less predicate you pass to it.

Something like that.

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re[2]: sorted?

[Stefan Schmiedl]

------ Original Message ------
From tomas@tuxteam.de
To guile-user@gnu.org
Date 09.12.2024 12:42:22
Subject Re: sorted?

>On Mon, Dec 09, 2024 at 11:37:33AM +0000, Ricardo G. Herdt wrote:
>>  Hi Jeremy,
>>
>>  Am 09.12.2024 11:21 schrieb Jeremy Korwin-Zmijowski:
>>  > The reference says :
>>  >
>>  >    Scheme Procedure: *sorted?* items less
>>  >    C Function: *scm_sorted_p* (items, less)
>>  >
>>  >        Return |#t| if items is a list or vector such that, for each
>>  >        element x and the next element y of items, |(less y x)| returns
>>  >        |#f|. Otherwise return |#f|.
>>  >
>>  > I think the description should be :
>>  >
>>  >    Return |#t| if items is a list or vector such that, for each element
>>  >    x and the next element y of items, |(less y x)| returns |#t|.
>>  >    Otherwise return |#f|.
>>
>>  Actually no, since less is applied to y and x in that order. This way
>>  (sorted? '(1 1) <) correctly returns #t as your experiments show.
>
>I don't get it. (< 1 1) is /always/ #f, regardless of the order of the
>ones?
>
>I'm as confused as Jeremy is.
>

I understand the reference text as "Return #t if the list is _not 
unsorted_".
Since (< 1 1) returns #f, '(1 1) is _not unsorted_ and all is well.

s.

Re: sorted?

[tomas]

[-- Attachment #1: Type: text/plain, Size: 1667 bytes --]

On Mon, Dec 09, 2024 at 01:54:47PM +0000, Stefan Schmiedl wrote:
> ------ Original Message ------
> > From tomas@tuxteam.de
> To guile-user@gnu.org
> Date 09.12.2024 12:42:22
> Subject Re: sorted?
> 
> > On Mon, Dec 09, 2024 at 11:37:33AM +0000, Ricardo G. Herdt wrote:
> > >  Hi Jeremy,
> > > 
> > >  Am 09.12.2024 11:21 schrieb Jeremy Korwin-Zmijowski:
> > >  > The reference says :
> > >  >
> > >  >    Scheme Procedure: *sorted?* items less
> > >  >    C Function: *scm_sorted_p* (items, less)
> > >  >
> > >  >        Return |#t| if items is a list or vector such that, for each
> > >  >        element x and the next element y of items, |(less y x)| returns
> > >  >        |#f|. Otherwise return |#f|.
> > >  >
> > >  > I think the description should be :
> > >  >
> > >  >    Return |#t| if items is a list or vector such that, for each element
> > >  >    x and the next element y of items, |(less y x)| returns |#t|.
> > >  >    Otherwise return |#f|.
> > > 
> > >  Actually no, since less is applied to y and x in that order. This way
> > >  (sorted? '(1 1) <) correctly returns #t as your experiments show.
> > 
> > I don't get it. (< 1 1) is /always/ #f, regardless of the order of the
> > ones?
> > 
> > I'm as confused as Jeremy is.
> > 
> 
> I understand the reference text as "Return #t if the list is _not
> unsorted_".
> Since (< 1 1) returns #f, '(1 1) is _not unsorted_ and all is well.

This seems the intention. But since it accepts an arbitrary "less"
function, it ends being iffy. How do you go from some "less" to a
"less-or-equal" without running into undecidability dark alleys?

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: sorted?

[Mikael Djurfeldt]

On Mon, Dec 9, 2024 at 2:11 PM <tomas@tuxteam.de> wrote:

> On Mon, Dec 09, 2024 at 01:58:08PM +0100, Mikael Djurfeldt wrote:
>
> [...]
>
> > No problem---I'm too.
> >
> > Think about it this way:
> >
> > How would you sort this list of numbers: 7 1 3 8 2 1 4 ?
> >
> > It's 1 1 2 3 4 7 8, right? That is what we want (sort '(7 1 3 8 2 1 4))
> to
> > output (+ the parentheses of course).
> >
> > Now, `sorted?' returns true if its input is what `sort' would have
> produced
> > as output, otherwise false.
>
> Hmmm. Perhaps, what throws me off the rails is that you can pass
> a "less" predicate to sorted?.
>
> To behave like it does, it has to have some notion of equality,
> which seems to be implicit and doesn't necessarily harmonize with
> the less predicate you pass to it.
>

(= a b) is equivalent to (not (or (< a b) (> a b)))

The reason why you need to pass less to sort is that sort needs a way to
determine when an object should go before another one. Let's for example
take the example of a list of neuronal spike events. Each event is (TIME .
ID). It could be unsorted because the data might come from different
detectors. To sort the list in time, we would call sort like this:

(sort '((0.73 . 7) (0.23 . 3) (0.54 . 17) (0.27 . 98)) (lambda (x y) (<
(car x) (car y))))

Note that in order for `sorted?' to determine if a list is sorted it needs
the same less predicate as `sort'.

There is actually to kinds of `sort'. Ordinary sort and stable sort. Stable
sort comes with a guarantee that if two objects are equal in terms of
"less" (i.e. neither x < y or x > y) they will appear in the output of the
stable sort in the same order they had in the input. Ordinary sort doesn't
have that guarantee but can be more efficient.

Re: sorted?

[Mikael Djurfeldt]

("two kinds of sort")

On Mon, Dec 9, 2024 at 7:32 PM Mikael Djurfeldt <mikael@djurfeldt.com>
wrote:

> On Mon, Dec 9, 2024 at 2:11 PM <tomas@tuxteam.de> wrote:
>
>> On Mon, Dec 09, 2024 at 01:58:08PM +0100, Mikael Djurfeldt wrote:
>>
>> [...]
>>
>> > No problem---I'm too.
>> >
>> > Think about it this way:
>> >
>> > How would you sort this list of numbers: 7 1 3 8 2 1 4 ?
>> >
>> > It's 1 1 2 3 4 7 8, right? That is what we want (sort '(7 1 3 8 2 1 4))
>> to
>> > output (+ the parentheses of course).
>> >
>> > Now, `sorted?' returns true if its input is what `sort' would have
>> produced
>> > as output, otherwise false.
>>
>> Hmmm. Perhaps, what throws me off the rails is that you can pass
>> a "less" predicate to sorted?.
>>
>> To behave like it does, it has to have some notion of equality,
>> which seems to be implicit and doesn't necessarily harmonize with
>> the less predicate you pass to it.
>>
>
> (= a b) is equivalent to (not (or (< a b) (> a b)))
>
> The reason why you need to pass less to sort is that sort needs a way to
> determine when an object should go before another one. Let's for example
> take the example of a list of neuronal spike events. Each event is (TIME .
> ID). It could be unsorted because the data might come from different
> detectors. To sort the list in time, we would call sort like this:
>
> (sort '((0.73 . 7) (0.23 . 3) (0.54 . 17) (0.27 . 98)) (lambda (x y) (<
> (car x) (car y))))
>
> Note that in order for `sorted?' to determine if a list is sorted it needs
> the same less predicate as `sort'.
>
> There is actually to kinds of `sort'. Ordinary sort and stable sort.
> Stable sort comes with a guarantee that if two objects are equal in terms
> of "less" (i.e. neither x < y or x > y) they will appear in the output of
> the stable sort in the same order they had in the input. Ordinary sort
> doesn't have that guarantee but can be more efficient.
>
>

Re: sorted?

[tomas]

[-- Attachment #1: Type: text/plain, Size: 1897 bytes --]

On Mon, Dec 09, 2024 at 07:32:09PM +0100, Mikael Djurfeldt wrote:
> On Mon, Dec 9, 2024 at 2:11 PM <tomas@tuxteam.de> wrote:
> 
> > On Mon, Dec 09, 2024 at 01:58:08PM +0100, Mikael Djurfeldt wrote:
> >
> > [...]
> >
> > > No problem---I'm too.
> > >
> > > Think about it this way:
> > >
> > > How would you sort this list of numbers: 7 1 3 8 2 1 4 ?
> > >
> > > It's 1 1 2 3 4 7 8, right? That is what we want (sort '(7 1 3 8 2 1 4))
> > to
> > > output (+ the parentheses of course).
> > >
> > > Now, `sorted?' returns true if its input is what `sort' would have
> > produced
> > > as output, otherwise false.
> >
> > Hmmm. Perhaps, what throws me off the rails is that you can pass
> > a "less" predicate to sorted?.
> >
> > To behave like it does, it has to have some notion of equality,
> > which seems to be implicit and doesn't necessarily harmonize with
> > the less predicate you pass to it.
> >
> 
> (= a b) is equivalent to (not (or (< a b) (> a b)))

Yes, but for that, you have to know what "=" is. Is it eq? Is it
eqv? Is it equal? (yeah, lame pun with question marks). Or is it
(see below)?

> The reason why you need to pass less to sort is that sort needs a way to
> determine when an object should go before another one. Let's for example
> take the example of a list of neuronal spike events. Each event is (TIME .
> ID). It could be unsorted because the data might come from different
> detectors. To sort the list in time, we would call sort like this:
> 
> (sort '((0.73 . 7) (0.23 . 3) (0.54 . 17) (0.27 . 98)) (lambda (x y) (<
> (car x) (car y))))

So here you'd need your equal to be (eq (car x) (car y)), right?

[...]

> There is actually to kinds of `sort'. Ordinary sort and stable sort.

Yes, I know that -- but this wasn't my issue (or at least I think it
isn't).

Thanks for your patience :)

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re[2]: sorted?

[Stefan Schmiedl]

------ Original Message ------
From tomas@tuxteam.de
To "Stefan Schmiedl" <s@xss.de>
Cc guile-user@gnu.org
Date 09.12.2024 15:10:18
Subject Re: sorted?

>On Mon, Dec 09, 2024 at 01:54:47PM +0000, Stefan Schmiedl wrote:
>>  ------ Original Message ------
>>  > From tomas@tuxteam.de
>>  To guile-user@gnu.org
>>  Date 09.12.2024 12:42:22
>>  Subject Re: sorted?
>>
>>  > On Mon, Dec 09, 2024 at 11:37:33AM +0000, Ricardo G. Herdt wrote:
>>  > >  Hi Jeremy,
>>  > >
>>  > >  Am 09.12.2024 11:21 schrieb Jeremy Korwin-Zmijowski:
>>  > >  > The reference says :
>>  > >  >
>>  > >  >    Scheme Procedure: *sorted?* items less
>>  > >  >    C Function: *scm_sorted_p* (items, less)
>>  > >  >
>>  > >  >        Return |#t| if items is a list or vector such that, for each
>>  > >  >        element x and the next element y of items, |(less y x)| returns
>>  > >  >        |#f|. Otherwise return |#f|.
>>  > >  >
>>  > >  > I think the description should be :
>>  > >  >
>>  > >  >    Return |#t| if items is a list or vector such that, for each element
>>  > >  >    x and the next element y of items, |(less y x)| returns |#t|.
>>  > >  >    Otherwise return |#f|.
>>  > >
>>  > >  Actually no, since less is applied to y and x in that order. This way
>>  > >  (sorted? '(1 1) <) correctly returns #t as your experiments show.
>>  >
>>  > I don't get it. (< 1 1) is /always/ #f, regardless of the order of the
>>  > ones?
>>  >
>>  > I'm as confused as Jeremy is.
>>  >
>>
>>  I understand the reference text as "Return #t if the list is _not
>>  unsorted_".
>>  Since (< 1 1) returns #f, '(1 1) is _not unsorted_ and all is well.
>
>This seems the intention. But since it accepts an arbitrary "less"
>function, it ends being iffy. How do you go from some "less" to a
>"less-or-equal" without running into undecidability dark alleys?
>
Well, the iffyness is managed by the programmer, who chooses the
comparison function.

Do you have an example of such an iffy set?

s.

Re: sorted?

[tomas]

[-- Attachment #1: Type: text/plain, Size: 872 bytes --]

On Mon, Dec 09, 2024 at 07:14:10PM +0000, Stefan Schmiedl wrote:
> ------ Original Message ------
> > From tomas@tuxteam.de

[...]

> > This seems the intention. But since it accepts an arbitrary "less"
> > function, it ends being iffy. How do you go from some "less" to a
> > "less-or-equal" without running into undecidability dark alleys?
> > 
> Well, the iffyness is managed by the programmer, who chooses the
> comparison function.
> 
> Do you have an example of such an iffy set?

I think Mikael just posted one, in another arm of this thread
(comparing pairs where only the car is relevant, i.e.

  (lambda (p1 p2) (< (car p1) (car p2)))

Then you'd need a corresponding equal, because otherwise you
end up with things which are neither less nor equal nor greater,
i.e. the ordering isn't total, which is bad for sorting :)

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: sorted?

[Mikael Djurfeldt]

On Mon, Dec 9, 2024 at 7:59 PM <tomas@tuxteam.de> wrote:

> > (= a b) is equivalent to (not (or (< a b) (> a b)))
>
> Yes, but for that, you have to know what "=" is. Is it eq? Is it
> eqv? Is it equal? (yeah, lame pun with question marks). Or is it
> (see below)?
>

It's equal in the sense of (not (or (< a b) (> a b)). If < is Scheme <
(i.e. comparing numbers), then this is completely equivalent with Scheme =.


> > The reason why you need to pass less to sort is that sort needs a way to
> > determine when an object should go before another one. Let's for example
> > take the example of a list of neuronal spike events. Each event is (TIME
> .
> > ID). It could be unsorted because the data might come from different
> > detectors. To sort the list in time, we would call sort like this:
> >
> > (sort '((0.73 . 7) (0.23 . 3) (0.54 . 17) (0.27 . 98)) (lambda (x y) (<
> > (car x) (car y))))
>
> So here you'd need your equal to be (eq (car x) (car y)), right?
>

As I've tried to convey, you don't need equal when sorting using `sort'.
But the equal corresponding to < is = in Scheme.

Re: sorted?

[Mikael Djurfeldt]

On Mon, Dec 9, 2024 at 8:23 PM <tomas@tuxteam.de> wrote:

>   (lambda (p1 p2) (< (car p1) (car p2)))
>
> Then you'd need a corresponding equal, because otherwise you
> end up with things which are neither less nor equal nor greater,
> i.e. the ordering isn't total, which is bad for sorting :)
>

`sort' assumes that the elements belong to a "strict total order", which
means that the connectedness-axiom is true, which means that a = b is
*equivalent to* not (a < b or a > b). So, we don't need equal.

Re: sorted?

[Mikael Djurfeldt]

On Mon, Dec 9, 2024 at 8:45 PM Mikael Djurfeldt <mikael@djurfeldt.com>
wrote:

> On Mon, Dec 9, 2024 at 8:23 PM <tomas@tuxteam.de> wrote:
>
>>   (lambda (p1 p2) (< (car p1) (car p2)))
>>
>> Then you'd need a corresponding equal, because otherwise you
>> end up with things which are neither less nor equal nor greater,
>> i.e. the ordering isn't total, which is bad for sorting :)
>>
>
> `sort' assumes that the elements belong to a "strict total order", which
> means that the connectedness-axiom is true, which means that a = b is
> *equivalent to* not (a < b or a > b). So, we don't need equal.
>

Actually, a "total order" is sufficient for `sort', because equal is not
necessary for sorting. I should have said that if we have a "strict total
order" (as is almost always the case) is sufficient for the equivalence I
have been talking about.

Re: sorted?

[tomas]

[-- Attachment #1: Type: text/plain, Size: 725 bytes --]

On Mon, Dec 09, 2024 at 08:45:33PM +0100, Mikael Djurfeldt wrote:
> On Mon, Dec 9, 2024 at 8:23 PM <tomas@tuxteam.de> wrote:
> 
> >   (lambda (p1 p2) (< (car p1) (car p2)))
> >
> > Then you'd need a corresponding equal, because otherwise you
> > end up with things which are neither less nor equal nor greater,
> > i.e. the ordering isn't total, which is bad for sorting :)
> >
> 
> `sort' assumes that the elements belong to a "strict total order", which
> means that the connectedness-axiom is true, which means that a = b is
> *equivalent to* not (a < b or a > b). So, we don't need equal.

I think we need one of = or >, which we both don't have. We just have <,
which is one too few.

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: sorted?

[Mikael Djurfeldt]

Den mån 9 dec. 2024 21:36 <tomas@tuxteam.de> skrev:

> On Mon, Dec 09, 2024 at 08:45:33PM +0100, Mikael Djurfeldt wrote:
> > On Mon, Dec 9, 2024 at 8:23 PM <tomas@tuxteam.de> wrote:
> >
> > >   (lambda (p1 p2) (< (car p1) (car p2)))
> > >
> > > Then you'd need a corresponding equal, because otherwise you
> > > end up with things which are neither less nor equal nor greater,
> > > i.e. the ordering isn't total, which is bad for sorting :)
> > >
> >
> > `sort' assumes that the elements belong to a "strict total order", which
> > means that the connectedness-axiom is true, which means that a = b is
> > *equivalent to* not (a < b or a > b). So, we don't need equal.
>
> I think we need one of = or >, which we both don't have. We just have <,
> which is one too few.
>

No :)

I won't argue further, but for future reference I want to be more precise:
For the sort algorithms in Guile (and in C++ and all other languages and
implementations where you pass a predicate to sort) to produce a
predictable result, the < passed as second argument needs to define a
"strict weak order" on the set to be sorted. In practice, you will very
seldom run into situations where the difference between the different kinds
of order come into play. (But the classes in the class precedence list in
GOOPS is a partial order, so it has to be topologically sorted.)

Best regards,
Mikael

>

RE: sorted?

[Maxime Devos via General Guile related discussions]

>Doing Advent of Code 2024, I was trying to use `sorted?` procedure. And 
something bothered me.
>
>The reference says :
>
>    Scheme Procedure: *sorted?* items less
>    C Function: *scm_sorted_p* (items, less)
>
>        Return |#t| if items is a list or vector such that, for each
>        element x and the next element y of items, |(less y x)| returns
>        |#f|. Otherwise return |#f|.
>
>I think the description should be :
>
>    Return |#t| if items is a list or vector such that, for each element
>    x and the next element y of items, |(less y x)| returns |#t|.
>    Otherwise return |#f|.
>

It shouldn’t. Let’s start with your example:

>Then, testing it in the REPL give me this :
>
>scheme@(guile-user)> (sorted? '(1 2 3) <)
>$13 = #t
>
>So far so good.
>
>scheme@(guile-user)> (sorted? '(3 2 1) <)
>$16 = #f

Consider the simpler case (sorted? '(1 2) <). This should, and does, return #true.

In this example, x=1 and y=2. Then, (less y x) is (< 2 1). This evaluates to #false. Since #false isn’t #true, according to the first description, (sorted? '(1 2) <) return #true. So, first description is ok in this case! Likewise, it is ok for (sorted? '(2 1) <).

However, the second description is wrong (just go over it step-by-step again if needed).

There is also another, more subtle thing going on. Conventionally, all values are truth values: everything not #false is considered to be ‘true’ (in Guile Scheme, also #nil is counted like #false I think, not sure). In Scheme, while a predicate (*) that is exposed (e.g. exported from a module) should produce only #t or #f as truth values (with some exceptions, like when it would prevent tail-calls, or when it invokes another caller-provided predicate that produces other truth values, it doesn’t need to normalise that), it’s usually fine for a predicate supplied by the caller (‘less’, in this case) to produce other truth values.

Because of that reason, it needs to be phrased in terms of #false instead of #true (actually #false->false, to account for #nil).

(*) in a general sense, also including multiple-variable relations.

>scheme@(guile-user)> (sorted? '(1 1) <)
$17 = #t

>I was expecting #f due to

>scheme@(guile-user)> (< 1 1)
>$18 = #f

By the second description, sure.
But by the first description, it is fine!

My guess is that it’s intentional, so that you can save one keystroke to write (sorted? '(1 1) <) instead of (sorted? '(1 2) <=).

Although, the description could use a bit of expansion to make clear what happens in the case that two elements are equal, and put emphasis on it really being ‘less’, not ‘less-than-or-equal-to’.

Best regards,
Maxime Devos

RE: sorted?

[Maxime Devos via General Guile related discussions]

>On Mon, Dec 09, 2024 at 11:37:33AM +0000, Ricardo G. Herdt wrote:
>> Hi Jeremy,
>> 
>> Am 09.12.2024 11:21 schrieb Jeremy Korwin-Zmijowski:
>> > The reference says :
>> > 
>> >    Scheme Procedure: *sorted?* items less
>> >    C Function: *scm_sorted_p* (items, less)
>> > 
>> >        Return |#t| if items is a list or vector such that, for each
>> >        element x and the next element y of items, |(less y x)| returns
>> >        |#f|. Otherwise return |#f|.
>> > 
>> > I think the description should be :
>> > 
>> >    Return |#t| if items is a list or vector such that, for each element
>> >    x and the next element y of items, |(less y x)| returns |#t|.
>> >    Otherwise return |#f|.
>> 
>> Actually no, since less is applied to y and x in that order. This way
>> (sorted? '(1 1) <) correctly returns #t as your experiments show.
>I don't get it. (< 1 1) is /always/ #f, regardless of the order of the
ones?

Please read the description closely. (< 1 1) returns #false, so ‘sorted?’ returns #false according to the first description.

RE: sorted?

[Maxime Devos via General Guile related discussions]

Van: tomas@tuxteam.de
Verzonden: maandag 9 december 2024 15:11
Aan: Stefan Schmiedl
CC: guile-user@gnu.org
Onderwerp: Re: sorted?

On Mon, Dec 09, 2024 at 01:54:47PM +0000, Stefan Schmiedl wrote:
> ------ Original Message ------
> > From tomas@tuxteam.de
> To guile-user@gnu.org
> Date 09.12.2024 12:42:22
> Subject Re: sorted?
> 
> > On Mon, Dec 09, 2024 at 11:37:33AM +0000, Ricardo G. Herdt wrote:
> > >  Hi Jeremy,
> > > 
> > >  Am 09.12.2024 11:21 schrieb Jeremy Korwin-Zmijowski:
> > >  > The reference says :
> > >  >
> > >  >    Scheme Procedure: *sorted?* items less
> > >  >    C Function: *scm_sorted_p* (items, less)
> > >  >
> > >  >        Return |#t| if items is a list or vector such that, for each
> > >  >        element x and the next element y of items, |(less y x)| returns
> > >  >        |#f|. Otherwise return |#f|.
> > >  >
> > >  > I think the description should be :
> > >  >
> > >  >    Return |#t| if items is a list or vector such that, for each element
> > >  >    x and the next element y of items, |(less y x)| returns |#t|.
> > >  >    Otherwise return |#f|.
> > > 
> > >  Actually no, since less is applied to y and x in that order. This way
> > >  (sorted? '(1 1) <) correctly returns #t as your experiments show.
> > 
> > I don't get it. (< 1 1) is /always/ #f, regardless of the order of the
> > ones?
> > 
> > I'm as confused as Jeremy is.
> > 
> 
> I understand the reference text as "Return #t if the list is _not
> unsorted_".
> Since (< 1 1) returns #f, '(1 1) is _not unsorted_ and all is well.

>This seems the intention. But since it accepts an arbitrary "less"
function, it ends being iffy. How do you go from some "less" to a
"less-or-equal" without running into undecidability dark alleys?

It doesn’t, though? It only accepts “less” (well, it technically also accept “less-or-equal”, but when two neighbouring elements are equal, you probably wouldn’t consider the result desirable(*)). I don’t have guile on this machine, but going by the (first) description, (sorted? '(1 1) <=) would be #false.

(*): possible exception: if you want to check both whether it is sorted and whether it doesn’t have duplicates, then (sorted? the-list <=) is fine. Counter-intuitively phrased, sure, but it would do the job.

FWIW, you can convert between “less” and “less-than-or-equal-to”:

X < Y ⇔ not (Y <= X)
X <= Y ⇔ not (Y < X)

Furthermore, you can define equality in terms of inequality:

X != Y ⇔ X<Y or Y<X
X = Y ⇔ X<=Y and Y<=X

Hence, it doesn’t really matter whether it accepts “less”, or whether it accepts “less-or-equal”, as long as the choice is documented, and the documentation agrees with the implementation (and with any applicable standards). 

All this said, I think it would have been better if ‘sorted?’ asked for a ‘less-or-equal’ predicate instead – would make the phrasing less awkward, and I’d guess it would make the implementation a bit simpler too. Seems to late to change it though. 

Best regards,
Maxime Devos

RE: sorted?

[Maxime Devos via General Guile related discussions]

Van: tomas@tuxteam.de
Verzonden: maandag 9 december 2024 21:38
Aan: Mikael Djurfeldt
CC: Stefan Schmiedl; guile-user@gnu.org
Onderwerp: Re: sorted?

>On Mon, Dec 09, 2024 at 08:45:33PM +0100, Mikael Djurfeldt wrote:
>> On Mon, Dec 9, 2024 at 8:23 PM <tomas@tuxteam.de> wrote:
>> 
>> >   (lambda (p1 p2) (< (car p1) (car p2)))
>> >
>> > Then you'd need a corresponding equal, because otherwise you
>> > end up with things which are neither less nor equal nor greater,
>> > i.e. the ordering isn't total, which is bad for sorting :)
>> >
>> 
>> `sort' assumes that the elements belong to a "strict total order", which
>> means that the connectedness-axiom is true, which means that a = b is
>> *equivalent to* not (a < b or a > b). So, we don't need equal.
>
>I think we need one of = or >, which we both don't have. We just have <,
which is one too few.

You do have >, ‘a > b’ is the same as ‘b < a’. This usually isn’t mentioned in the axioms of orderings because it’s simply notation – whenever you mirror the symbol of a binary relation, that is simply notation for swapping the arguments (in logic those would be called terms I think) (a < b  = b > a).

From ‘<’, you have ‘=’, by the equivalence mentioned above.

Just because it’s not passed explicitly, doesn’t mean you don’t have it – you can derive ‘=’ from the axioms and some logic.

Did you see my previous mail, where I said pretty much the same as what Tomas is writing (except about sorted? instead of sort)?

Best regards,
Maxime Devos

RE: sorted?

[Maxime Devos via General Guile related discussions]

>Did you see my previous mail, where I said pretty much the same as what Tomas is writing (except about sorted? instead of sort)?

Nevermind this, my e-mail program had some issues.