delete does not work

[White_Owl]

Code: Select all

C:>clisp
...
Welcome to GNU CLISP 2.49 (2010-07-07) <http://clisp.cons.org/>
...

[1]> (setf lst '(1 2 3))
(1 2 3)
[2]> (delete 1 lst)
(2 3)
[3]> lst
(1 2 3)
[4]> (delete 2 lst)
(1 3)
[5]> lst
(1 3)
[6]> (delete 1 lst)
(3)
[7]> lst
(1 3)
[8]>

But I do not see any mentioning about first element in the list in documentation: http://clhs.lisp.se/Body/f_rm_rm.htm
Documentation lies? Is there a better documentation?

[pjstirling]

DELETE(-IF/-IF-NOT) isn't required to modify the list that you pass it, it can simply build a new list without the deleted item(s).

The key line is

delete, delete-if, and delete-if-not are like remove, remove-if, and remove-if-not respectively, but they may modify sequence.

To my knowledge in e.g. sbcl, the delete functions always act like the remove functions.

You should always use it as (SETF list (DELETE item list))

[White_Owl]

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????

[David Mullen]

I use these:

Code: Select all

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defun get-removal-macro-expansion (item place options environment function-name)
    (multiple-value-bind (temps vals news writer reader) (get-setf-expansion place environment)
      (let ((modification-form `(,function-name ,item ,reader ,@options)) (new (car news)))
        (unless (endp (cdr news)) (error "Multiple values aren't supported."))
        `(let* (,.(mapcar #'list temps vals) (,new ,modification-form))
           ,writer)))))

(defmacro deletef (item place &rest options &environment environment)
  (get-removal-macro-expansion item place options environment 'delete))

(defmacro removef (item place &rest options &environment environment)
  (get-removal-macro-expansion item place options environment 'remove))

Other people might switch the argument order—I think it's the other way around in Alexandria?

[pjstirling]

The DELETE functions are intended as a possible optimisation, an optimisation that no longer really makes sense.

The effort that ultimately resulted in the Common-lisp standard was started in 1981 (incidentally the year I was born). My first computer had eight thousand times less memory than my current machine, it didn't support virtual memory, and even if it had, it had two-hundred and fifty thousand times less storage attached.

Saving every byte is nowhere near as important as it used to be. (And there are other higher-level ways to save memory if that is the first consideration)

On the other hand, if you are using a generational garbage collector then modifying existing objects risks dirtying the pages for older generations which will increase your time spent in gc.

Or that's the reasoning that I picked up.

[sylwester]

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

[pjstirling]

Repeated REMOVE or DELETE is O(n^2) regardless (unless you supply count it must walk the whole list for each call)

The right way to empty a list is always a loop over POP

[sylwester]

Repeated REMOVE or DELETE is O(n^2) regardless (unless you supply count it must walk the whole list for each call)

The right way to empty a list is always a loop over POP

Absolutely not.. Im talking about space complexity and not time!

Remove n times is O(n^2) space since it makes n copies of every element extra is not removed.
delete does not copy structure and thus is O(1) space.

In both cases time complexity is O(n^2), but I didn't focus on time complexity in my post

[pjstirling]

Using a loop over POP is O(n) in both.

[White_Owl]

The DELETE functions are intended as a possible optimisation, an optimisation that no longer really makes sense.

Well... That does look plausible.

Well, after reading all these posts I came to a conclusion:
Do not use DELETE. Use (setf list (remove item list)). That would be much more reliable between all dialects of Lisp.