>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
