RE: sorted?

Van: [email protected]
Verzonden: maandag 9 december 2024 15:11
Aan: Stefan Schmiedl
CC: [email protected]
Onderwerp: Re: sorted?

On Mon, Dec 09, 2024 at 01:54:47PM +0000, Stefan Schmiedl wrote:
> ------ Original Message ------
> > From [email protected]
> To [email protected]
> 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