common-lisppractical-common-lisp

Destructive sorting in lisp


I'm reading Practical Common Lisp. In chapter 11, it says this about sorting:

Typically you won't care about the unsorted version of a sequence after you've sorted it, so it makes sense to allow SORT and STABLE-SORT to destroy the sequence in the course of sorting it. But it does mean you need to remember to write the following:

(setf my-sequence (sort my-sequence #'string<))

I tried the following code:

CL-USER> (defparameter *a* #( 8 4 3 9 5 9 2 3 9 2 9 4 3)) 
*A*            
CL-USER> *a*
#(8 4 3 9 5 9 2 3 9 2 9 4 3)                                     
CL-USER> (sort *a* #'<)
#(2 2 3 3 3 4 4 5 8 9 9 9 9)
CL-USER> *a*
#(2 2 3 3 3 4 4 5 8 9 9 9 9)

In this code we can see that the variable *a* has been changed by the sort function.

Then why do the book say that is necessary to do an assignment?

I'm using SBCL + Ubuntu 14.04 + Emacs + Slime

EDIT: Following the comment of @Sylwester I add the evaluation of *a* so it's clear that the value has been changed.


Solution

  • It's necessary to do the assignment if you want your variable to contain the proper value of the sorted sequence afterwards. If you don't care about that and only want the return value of sort, you don't need an assignment.

    There are two reasons for this. First, an implementation is allowed to use non-destructive copying to implement destructive operations. Secondly, destructive operations on lists can permute the conses such that the value passed into the operation no longer points to the first cons of the sequence.

    Here's an example of the second problem (run under SBCL):

    (let ((xs (list 4 3 2 1)))
      (sort xs '<)
      xs)
    => (4)
    

    If we add the assignment:

    (let ((xs (list 4 3 2 1)))
      (setf xs (sort xs '<))
      xs)
    => (1 2 3 4)