If I do:
(setq x (list 5 3 2 1 4))
=> (5 3 2 1 4)
(sort x #'<)
=> (1 2 3 4 5)
is it now guaranteed that X is EQUAL to one of (1 2 3 4 5) or
(5 3 2 1 4), or perhaps some other permutation of the original list?
Under SORT in the Hyperspec, I can't find an explicit statement on the
matter, although there's an example that I think relies on this -- in
the call of STABLE-SORT, the thing being sorted has already been
sorted by SORT.
Some relevant pieces of the Hyperspec, apart from the example under
SORT, are:
From the entry for SORT:
The sorting operation can be destructive in all cases. ... In the
case of a list, the list is destructively reordered in the same
manner as for nreverse.
From the entry for NREVERSE:
reverse and nreverse differ in that reverse always creates and
returns a new sequence, whereas nreverse might modify and
return the given sequence
For nreverse, sequence might be destroyed and re-used to produce
the result. The result might or might not be identical to
sequence.
To make sense of this, I'm wondering whether NREVERSE guarantees that
its result is identical to sequence in the case that the sequence is
modified. But I don't think there's an explicit statement to that
effect.
In article <·················@news.dircon.co.uk>,
Simon Katz <·····@nomistech.com> wrote:
>If I do:
>
> (setq x (list 5 3 2 1 4))
> => (5 3 2 1 4)
>
> (sort x #'<)
> => (1 2 3 4 5)
>
>is it now guaranteed that X is EQUAL to one of (1 2 3 4 5) or
>(5 3 2 1 4), or perhaps some other permutation of the original list?
No. There's a good chance that X will be (5). An implementation may do
the sorting by relinking the cdrs, but leaving all the cars unchanged. X
refers to the cons whose car is 5 before calling SORT, and if this is how
SORT is implemented it will continue to refer to that cons when it's done.
But now that cons's cdr will be NIL, since it's now the last cons in the
list instead of the first one.
>Under SORT in the Hyperspec, I can't find an explicit statement on the
>matter, although there's an example that I think relies on this -- in
>the call of STABLE-SORT, the thing being sorted has already been
>sorted by SORT.
>
>Some relevant pieces of the Hyperspec, apart from the example under
>SORT, are:
>
> From the entry for SORT:
>
> The sorting operation can be destructive in all cases. ... In the
> case of a list, the list is destructively reordered in the same
> manner as for nreverse.
>
> From the entry for NREVERSE:
>
> reverse and nreverse differ in that reverse always creates and
> returns a new sequence, whereas nreverse might modify and
> return the given sequence
>
> For nreverse, sequence might be destroyed and re-used to produce
> the result. The result might or might not be identical to
> sequence.
>
>To make sense of this, I'm wondering whether NREVERSE guarantees that
>its result is identical to sequence in the case that the sequence is
>modified. But I don't think there's an explicit statement to that
>effect.
It explicitly says that the result might *not* be identical. In most
implementations, the result will *not* be identical except when sequence
has zero or one elements. Almost all implementations of NREVERSE work by
relinking the cdrs. So the cons that was originally first will be last and
vice versa.
--
Barry Margolin, ······@genuity.net
Genuity, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
I wrote in message ······················@news.dircon.co.uk...
> If I do:
>
> (setq x (list 5 3 2 1 4))
> => (5 3 2 1 4)
>
> (sort x #'<)
> => (1 2 3 4 5)
>
> is it now guaranteed that X is EQUAL to one of (1 2 3 4 5) or
> (5 3 2 1 4), or perhaps some other permutation of the original list?
>
>
> Under SORT in the Hyperspec, I can't find an explicit statement on
> the matter, although there's an example that I think relies on
> this -- in the call of STABLE-SORT, the thing being sorted has
> already been sorted by SORT.
Whoops!
The example I'm referring to sorts a vector, not a list.
I'm no longer confused.
"Simon Katz" <·····@nomistech.com> writes:
> If I do:
>
> (setq x (list 5 3 2 1 4))
> => (5 3 2 1 4)
>
> (sort x #'<)
> => (1 2 3 4 5)
>
> is it now guaranteed that X is EQUAL to one of (1 2 3 4 5) or
> (5 3 2 1 4), or perhaps some other permutation of the original list?
No. Destructive functions are permitted, but not required to
destructively modify the values passed in, i.e. sort is always allowed
to just create a new copy of list. Furthermore since sort can't
modify the binding of x, the value that x is bound to after a call to
a destructive function on the value of x is unspecified. You will
always have to do
(setq x (sort x #'<))
if you want x to be bound to the sorted list.
Regs, Pierre.
--
Pierre R. Mai <····@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein
Simon Katz wrote:
>
> If I do:
>
> (setq x (list 5 3 2 1 4))
> => (5 3 2 1 4)
>
> (sort x #'<)
> => (1 2 3 4 5)
>
> is it now guaranteed that X is EQUAL to one of (1 2 3 4 5) or
> (5 3 2 1 4), or perhaps some other permutation of the original list?
Sorts trash their input. We have a safe-sort to leave the input as is.
LISP(2): (setq x (list 5 3 2 1 4))
(5 3 2 1 4)
LISP(3): (setq y (sort x #'<))
(1 2 3 4 5)
LISP(4): x
(5)
LISP(5): y
(1 2 3 4 5)
LISP(6): (setq w (list 5 3 2 1 4))
(5 3 2 1 4)
LISP(7): (setq z (stable-sort w #'<))
(1 2 3 4 5)
LISP(8): w
(5)
LISP(9): z
(1 2 3 4 5)
LISP(10): (setq u (list 5 3 2 1 4))
(5 3 2 1 4)
LISP(11): (setq v (safe-sort u #'<))
(1 2 3 4 5)
LISP(12): u
(5 3 2 1 4)
LISP(13): v
(1 2 3 4 5)
"Jeff Sandys" <·······@asme.org> wrote in message
······················@asme.org...
> Simon Katz wrote:
> >
> > If I do:
> >
> > (setq x (list 5 3 2 1 4))
> > => (5 3 2 1 4)
> >
> > (sort x #'<)
> > => (1 2 3 4 5)
> >
> > is it now guaranteed that X is EQUAL to one of (1 2 3 4 5) or
> > (5 3 2 1 4), or perhaps some other permutation of the original
> > list?
>
> Sorts trash their input. We have a safe-sort to leave the input as
> is.
>
> LISP(2): (setq x (list 5 3 2 1 4))
> (5 3 2 1 4)
> LISP(3): (setq y (sort x #'<))
> (1 2 3 4 5)
> LISP(4): x
> (5)
FWIW, in LispWorks for Windows 4.1.20:
CL-USER 2 > (setq x (list 5 3 2 1 4))
(5 3 2 1 4)
CL-USER 3 > (setq y (sort x #'<))
(1 2 3 4 5)
CL-USER 4 > x
(1 2 3 4 5)
I know now that this is not to be relied upon, but when I saw this
behaviour, together with the example in the Hyperspec that sorts
vectors, I started to get confused.
> [further examples deleted]
> LISP(11): (setq v (safe-sort u #'<))
> (1 2 3 4 5)
> LISP(12): u
> (5 3 2 1 4)
> LISP(13): v
> (1 2 3 4 5)
Common Lisp does not have a SAFE-SORT function, though of course it's
easy to write one that copies the sequence before sorting.
In article <·················@news.dircon.co.uk>,
Simon Katz <·····@nomistech.com> wrote:
>"Jeff Sandys" <·······@asme.org> wrote in message
>······················@asme.org...
>> Sorts trash their input. We have a safe-sort to leave the input as
>> is.
>>
>> LISP(2): (setq x (list 5 3 2 1 4))
>> (5 3 2 1 4)
>> LISP(3): (setq y (sort x #'<))
>> (1 2 3 4 5)
>> LISP(4): x
>> (5)
>
>FWIW, in LispWorks for Windows 4.1.20:
>
> CL-USER 2 > (setq x (list 5 3 2 1 4))
> (5 3 2 1 4)
>
> CL-USER 3 > (setq y (sort x #'<))
> (1 2 3 4 5)
>
> CL-USER 4 > x
> (1 2 3 4 5)
FWIW, GNU Emacs Lisp gets the same result Jeff Sandys did:
(setq x (list 5 4 3 2 1))
(5 4 3 2 1)
(sort x #'<)
(1 2 3 4 5)
x
(5)
LispWorks presumably works by modifying CARs, the others work by modifying
CDRs. Both techniques are allowed by the standard, and applications should
be written in such a way that they'll work with either.
--
Barry Margolin, ······@genuity.net
Genuity, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.