Van: to...@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 to...@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
