普通的Lisp排序函数，从原始列表中删除一个元素

Question

我使用SBCL当我像下面这样使用sort函数时，

CL-USER> (defparameter y '(5 7 2 9 4 6))
Y
CL-USER> y
(5 7 2 9 4 6)
CL-USER> (sort y #'>)
(9 7 6 5 4 2)
CL-USER> y
(7 6 5 4 2)

最大的元素(在本例中为9)从原始列表中删除。

想知道发生了什么事吗?

Answer 1

sort，根据手册，

根据谓词函数确定的顺序对序列进行破坏性排序。

换句话说，它可以修改它的实参，并且您应该得到作为排序操作结果的返回值。

CL-USER> (defvar y (list 5 7 2 9 4 6))
Y
CL-USER> (setf y (sort y #'>))
(9 7 6 5 4 2)
CL-USER> y
(9 7 6 5 4 2)

注意，因为它可以修改它的参数，如果我们想要避免这样的修改，应该用copy-list来调用它:

CL-USER> (defparameter y '(5 7 2 9 4 6))
Y
CL-USER> (sort (copy-list y) #'<)
(2 4 5 6 7 9)
CL-USER> y
(5 7 2 9 4 6)

最后，注意修改文字值(如'(5 7 2 9 4 6))可能产生未定义的行为，应该避免。

Answer 2

(defvar *y* '(1 2 3))

所以*y*指向(1 2 3)。这样的。

*y*--->[*|*]--->[*|*]--->[*|*]---> NIL
|        |        |
v        v        v
1        2        3

现在如果你计算(sort *y* #'>)，那么*y*首先被计算，内容被传递给sort。不是变量，而是内容!在函数sort内部，没有可用的*y*引用。sort得到的是对第一个cons单元格的引用。

现在，当sort将3移动到前面时，它可以通过在前面放置一个新的cons单元格来做到这一点(这是实现排序的一种方法)。但是sort永远不能更新*y*来引用不同的对象，因为它没有引用*y*本身，而是引用(1 2 3)的第一个cons单元格。

因此，sort返回一个排序列表，并且应该使用它作为结果，而不是使用指向原始参数的引用。原始参数列表可能已被更改:

sort也可能是破坏性的.

注意:在Common Lisp中没有指定破坏性排序的确切行为

因此实现可能显示不同的副作用。参见CLISP实现示例:

[1]> (defvar *y* '(1 2 3))
*Y*
[2]> (sort *y* #'>)
(3 2 1)
[3]> *y*
(3 2 1)