sort behavior is strange

[Jinsong Zhao]

Hi there,

I hope to sort an associate list with #'sort. I tried something as follows:

* (setf zzz (pairlis '(a b c d e) '(2 4 5 1 3)))
((E . 3) (D . 1) (C . 5) (B . 4) (A . 2))
* (stable-sort zzz #'< :key #'cdr)
((D . 1) (A . 2) (E . 3) (B . 4) (C . 5))
* zzz
((D . 1) (A . 2) (E . 3) (B . 4) (C . 5))

It works as expected.

* (setf zzz (pairlis '(a b c d e) '(2 4 5 1 3)))
((E . 3) (D . 1) (C . 5) (B . 4) (A . 2))
* (stable-sort zzz #'> :key #'cdr)
((C . 5) (B . 4) (E . 3) (A . 2) (D . 1))
* zzz
((E . 3) (A . 2) (D . 1))

I just do not know why zzz is only 3 members?

Best,
Jinsong

[Lieven Marchand]

sort is destructive so you should assign the result back to the variable
is you want to retain the whole list, like (setf zzz (stable-sort zzz
#'> :key #'cdr)). sort rearranges the cells of its argument and
otherwise zzz keeps pointing to one of the cells in the list. In the
first case you got lucky, in the second case you didn't.

--
Laat hulle almal sterf. Ek is tevrede om die wêreld te sien brand en die vallende
konings te spot. Ek en my aasdier sal loop op die as van die verwoeste aarde.

[Tom Russ]

On Thursday, April 20, 2023 at 8:31:00 AM UTC-7, Lieven Marchand wrote:
> Jinsong Zhao <jsz...@yeah.net> writes:
>
> > I hope to sort an associate list with #'sort. I tried something as follows:
> >
> > * (setf zzz (pairlis '(a b c d e) '(2 4 5 1 3)))
> > ((E . 3) (D . 1) (C . 5) (B . 4) (A . 2))
> > * (stable-sort zzz #'< :key #'cdr)
> > ((D . 1) (A . 2) (E . 3) (B . 4) (C . 5))
> > * zzz
> > ((D . 1) (A . 2) (E . 3) (B . 4) (C . 5))
> >
> > It works as expected.
> >
> > * (setf zzz (pairlis '(a b c d e) '(2 4 5 1 3)))
> > ((E . 3) (D . 1) (C . 5) (B . 4) (A . 2))
> > * (stable-sort zzz #'> :key #'cdr)
> > ((C . 5) (B . 4) (E . 3) (A . 2) (D . 1))
> > * zzz
> > ((E . 3) (A . 2) (D . 1))
> >
> > I just do not know why zzz is only 3 members?
> sort is destructive so you should assign the result back to the variable
> is you want to retain the whole list, like (setf zzz (stable-sort zzz
> #'> :key #'cdr)). sort rearranges the cells of its argument and
> otherwise zzz keeps pointing to one of the cells in the list. In the
> first case you got lucky, in the second case you didn't.

And if you don't want to alter the input list, you would need to call COPY-LIST
or COPY-TREE on it, depending on how much sharing of cons cells you want
between the lists.

[Kaz Kylheku]

On 2023-04-20, Lieven Marchand <m...@wyrd.be> wrote:
> Jinsong Zhao <jsz...@yeah.net> writes:
>
>> I hope to sort an associate list with #'sort. I tried something as follows:
>>
>> * (setf zzz (pairlis '(a b c d e) '(2 4 5 1 3)))
>> ((E . 3) (D . 1) (C . 5) (B . 4) (A . 2))
>> * (stable-sort zzz #'< :key #'cdr)
>> ((D . 1) (A . 2) (E . 3) (B . 4) (C . 5))
>> * zzz
>> ((D . 1) (A . 2) (E . 3) (B . 4) (C . 5))
>>
>> It works as expected.
>>
>> * (setf zzz (pairlis '(a b c d e) '(2 4 5 1 3)))
>> ((E . 3) (D . 1) (C . 5) (B . 4) (A . 2))
>> * (stable-sort zzz #'> :key #'cdr)
>> ((C . 5) (B . 4) (E . 3) (A . 2) (D . 1))
>> * zzz
>> ((E . 3) (A . 2) (D . 1))
>>
>> I just do not know why zzz is only 3 members?
>
> sort is destructive so you should assign the result back to the variable

That is not the correct reason. In fact only a destructive sort could
possibly achieve the requirement of "I want to sort a list which comes
from a variable, such that the list in the variable appears sorted,
without assigning to the variable".


--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazi...@mstdn.ca

[Kaz Kylheku]

Sort is destructive, which is why you are seeing any change in the value
of the variable. You are expecting that; i.e. you expect sort to change
the list in place. Just not the surprising results of seeing just part
of the list.

Sort can work in three possible ways (or any mixture thereof):

1. It can keep the list structure exactly the same, and move the values
among the list's cells. If that is the case, you will see the
naively expected behavior that the value of the variable will hold
a sorted list.

2. It can keep elements in their respective cells but rearrange the
cells into a different shape.

3. It can allocate new cells.

Only if a sort implementation strictly followes destructive approach
(1), would you get the expected behavior that the variable turns into
the sorted list.

Because (2) and (3) are allowed, you must capture the return value of
sort (and store it into the variable). Only the return value is
required to be the sorted list. The original head cons cell passed into
the function is not required to be the head of the sorted list,
and, additionally, may be altered.