Destructive sorting in lisp
I am reading Practical Common Lisp. In chapter 11, this talks about sorting:
Typically, after sorting, you won't care about the unsorted version of the sequence, so it makes sense to resolve
SORT
andSTABLE-SORT
destroy the sequence while you sort it. But that means you need to remember 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 has *a*
been changed by the function SORT
.
Then why does the book say the task must be completed?
I am using SBCL + Ubuntu 14.04 + Emacs + Slime
EDIT:
Following @ Sylwester's comment, I am adding an evaluation *a*
to make it clear that the value has changed.
source to share
An assignment is necessary if you want your variable to subsequently contain the correct value of the ordered sequence. If you don't care and you only need to return a value sort
, then you don't need to assign.
There are two reasons for this. First, implementations are allowed to use non-destructive copying to implement destructive operations. Second, destructive list operations can rearrange the ends so that the value passed to the operation no longer points to the first cons of the sequence.
Here is an example of the second problem (performed under SBCL):
(let ((xs (list 4 3 2 1)))
(sort xs '<)
xs)
=> (4)
If we add an assignment:
(let ((xs (list 4 3 2 1)))
(setf xs (sort xs '<))
xs)
=> (1 2 3 4)
source to share
The variable cannot be changed by the sort function because the sort function is not aware of the variable at all.
The entire sort function receives a vector or a list, but not variables.
In Common Lisp, sorting can be destructive. When it receives a vector to sort, it can return the same vector or a new one. It depends on the implementation. In one implementation, it can return the same vector, and in another, it can return a new one. But in any case, they will be sorted.
If there is a variable that points to a sequence and for which the author expects it to be after sorting into a sorted sequence: set the variable to the result of the sort operation. Otherwise, there may be cases where, after a potentially destructive sort, the variable will not point to the SORT result, but still an unsorted or otherwise modified sequence. In the case of a vector, this MAY be an old and unsorted vector.
REMEMBER The only thing you can be sure of is that the SORT function returns the sorted sequence as its value.
source to share