Re: sorted?

[Mikael Djurfeldt]

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