delete does not work

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?

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

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

I use these:

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

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.

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:

  (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

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

pjstirling wrote: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

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

pjstirling wrote: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.

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

pop does a setq. It won't alter the argument. In my description I'm doing consecutive delete of random elements until I'm at one last using double loop will end up being O(n^2) time and O(1) space. By making the delete O(1), as in hash, you can get it O(n) time in total.

delete is not about time complexity. It's about space complexity. Using remove will cons n^2 times. eg, a small list of a million elements will cons 8TB memory on a 64 bit machine while none by using delete. If you want a functional interface you copy the initial list ie. cons 8MB. It sure beats 8TB memory usage. When you have a copy using delete in place of remove is not possible to detect by the user except perhaps the user gets the result the same day.

It says something about the appeal and tractability of Lisp's lists that we're talking about million-element lists. I mean, you could argue for a vector because that would halve the per-element overhead. But it's kind of hard to beat the sheer handiness of lists. It's why we all (most of us, anyway) reach for lists first, despite the other structures on the menu. (And, hey, they've worked out pretty well for representing source code.)

Not using mutating functions is the way to go when developing since you don't want to spend time micro optimizing code that does not need optimization.
delete *is* compatible with remove in every implementation of Common Lisp so I don't understand how you can state remove is more compatible.
As long as you, in the same way as remove, use the returned value you are in the clear with both functions.