On Mon, Dec 9, 2024 at 2:11 PM <to...@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.
