Re: sorted?

[Mikael Djurfeldt]

("two kinds of sort")

On Mon, Dec 9, 2024 at 7:32 PM Mikael Djurfeldt <mikael@djurfeldt.com>
wrote:

> 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.
>
>