White_Owl wrote:If delete always mimic remove and at the same time does not always modify the original list - what is the point of having the delete functions????
Imagine this code:
Code: Select all
(defparameter *lst* (list 1 2 3))
(delete 1 (list 1 2 3))
(delete 1 *lst*)
(delete 2 (list 1 2 3))
(delete 2 *lst*)
Now since delete is a function the fact that the second argument is a expression that evaluates to structure in the first and variable that evaluates to a structure in the second has nothing to do with the outcome. By the time the code runs the list is just an address pointer to the list.
To do a destructive delete the item to be deleted it cannot be the first element. It's because a destuctive delete redirects the cdr of the previous cons to the rest of the chain from the element to be deleted. However since the function works the same as remove you should always take the returned value as the result and thus what happens when the deleted element is the first elemet is just a cdr on the argument. The variable that pointed to the first cons still points to the same pair and it points to the rest of the list.
In the second version you see it's the second element and in most implementation this usually means that it will destructivly change the first pair to point to the third before returning the argument. *lst* points to the same location as before but that list has undergone destructive change. Because of this the standard just says mutating is optional so if you make a CL implementation and just make delete an alias for remove you are in the clear. However serious implementations wouldn't do that since delete is guaranteed O(1) space while remove is always O(n) space.
If you do delete continuously on a structure until you have one element left the making a copy and then use delete instead of remove will use O(n) space instead of O(n^2) which would give gc a lot of unnecessary work. For a small list you wouldn't notice it and you shuldn't care, but imagine you did it with millions of elements. Then you would benefit from the space saving. This examlpe might fix itself by using a hash so it isn't a very good example for using delete