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

>