DELETE is destructive — but not always?

问题:

I'm a little confused about Common Lisp's destructive DELETE function. It seems to work as expected, except for if the item is the first item on the list:

CL-USER> (defvar *test* (list 1 2 3))
*TEST*
CL-USER> (delete 1 *test*)
(2 3)
CL-USER> *test*
(1 2 3)
CL-USER> (delete 2 *test*)
(1 3)
CL-USER> *test*
(1 3)

回答1:

"Destructive" does not mean "operates in place". It means that the structure of the value operated on might be modified in some arbitrary and often undefined way. This can in some instances, implementations and cases have an effect as if it was "in place". This can generally not be relied upon, however.

If you use a destructive operator, you are telling the compiler that you are not interested in the previous value of the variable after the operation is complete. You should assume that that value is garbled beyond recognition afterwards and not use it anymore. Instead, you should use the return value of the operation.

(let ((a (list 1 2 3)))
  (let ((b (delete 2 a)))
    (frob b))
  a)

=> You were eaten by a grue.

If you are unsure of the safety of destructive operations, use their non-destructive counterparts (remove in this case).

(let ((a (list 1 2 3)))
  (let ((b (remove 2 a)))
    (frob b))
  a)

=> (1 2 3)

If you really want to modify the contents of a variable, set them to the return value of the operation:

(let ((a (list 1 2 3)))
  (setf a (delete 2 a))
  a)

=> (1 3)

回答2:

Keep in mind that DELETE is supposed to work on the list, and not on a variable. DELETE gets passed the list (a pointer to the first cons) and not the variable.

Since delete does not have access to the variable *test*, it can't change it. 'It' here means its bindings. *test* will point to the same cons cell as before. The only thing that can be changed is the contents of the cons cell or the contents of other cons cells the first cons cell is pointing to.

One thing is sure, no matter what DELETE does, *test* will always point to the same cons cell.

What follows from that? If you want to have *test* point to the result of the delete operation, then you explicitly have to say so:

(setq *test* (delete 1 *test*))

回答3:

DELETE works by changing the CDR of the previous cons cell of the list to point to the one past the element(s) being deleted. But if you're deleting the first element of the list, there is no previous cons cell to modify.

Although this implementation isn't actually specified by the language standard, it's the way practically every implementation works.

Since there's no previous cons cell to modify when deleting the first element of the list, it simply returns the second cons cell. So even though DELETE is permitted to modify the list, you still must assign the result to your variable to handle this case. Also, it should be emphasized that destructive behavior is only allowed by the standard, not required. So there's a remote possibility that some implementation might not implement it destructively at all, and you must allow for that as well.

And even if DELETE worked by modifying CARs instead of CDRs, there's still a case that it can't do destructively: deleting all the elements of a list, e.g.

(setq *test* (list 'a 'a))
(delete 'a *test*)

This results in an empty list, i.e. NIL. But *test* still contains the cons cell that was the head of the original list, and there's no way for DELETE to change that. So you must do:

(setq *test* (delete 'a *test*))

to set *test* to NIL.