RE: sorted?

>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