From: Joachim De Beule
Subject: confused about delete
Date: 
Message-ID: <m31yrjxud9.fsf@artipc5.vub.ac.be>
Hi all,

I am a bit confused by the effect of the lisp function DELETE.
It is supposed to be the destructive version of REMOVE but if you
DELETE the first element of a list, the list is not destructively
modified:

   (setf the-list '(a b c))
   => (a b c)
   (delete the-list 'a '(a b c))
   => (b c)
   the-list
   => (a b c)

Two Questions (number 2 more important):

1) Why is this the case?  (I can imagine it is difficult to get rid of
   the first cons cel of a list without losing the list itself but
   shouldn't DELETE take care of this anyway and help avoid people like me
   debugging for quite some time, getting frustrated because
   they don't understand what goes wrong?)

2) What is the sollution? Should I allways write something like
   
   (setf the-list (delete 'a the-list))

   to cope with having to delete the first element? Then what is the
   point of having a destructive version of remove anyway?
   
Regards and thanks, Joachim.

From: Hrvoje Niksic
Subject: Re: confused about delete
Date: 
Message-ID: <sxsy9tr5oyz.fsf@florida.arsdigita.de>
Joachim De Beule <·······@arti.vub.ac.be> writes:

> 1) Why is this the case?

Deleting elements destructively works by readjusting CDR to point to
the next location.  The first element is not pointed to by a CDR, but
by your list variable, of which DELETE knows nothing about.

> 2) What is the sollution? Should I allways write something like
>    
>    (setf the-list (delete 'a the-list))

Yes.

> Then what is the point of having a destructive version of remove
> anyway?

You misunderstood the purpose of DELETE: it is not about avoiding one
SETQ, it's about the reuse of memory.  Specifically, REMOVE *has* to
return a copy of the list (modulo the deleted element), whereas DELETE
is allowed to reuse the existing conses, readjusting them so that the
deletion appears done.

The distinction is crucial for complex shared structures: if the list
you're modifying is shared by other data structures, DELETE and REMOVE
will have drastically different results.
From: Martti Halminen
Subject: Re: confused about delete
Date: 
Message-ID: <3AC09849.4C1798CB@solibri.com>
Clemens Heitzinger wrote:
> 
> Joachim De Beule <·······@arti.vub.ac.be> writes:
> 
> > Hi all,
> >
> > I am a bit confused by the effect of the lisp function DELETE.
> > It is supposed to be the destructive version of REMOVE but if you
> 
> From the HyperSpec:
> 
> delete, delete-if, and delete-if-not are like remove, remove-if, and
> remove-if-not respectively, but they _may_ modify sequence.
> 
> > 2) What is the sollution? Should I allways write something like
> >
> >    (setf the-list (delete 'a the-list))
> >
> >    to cope with having to delete the first element? Then what is the
> >    point of having a destructive version of remove anyway?
> 
> Yes.  If you use this often, write a macro.

To amplify on this: the idea with the destructive versions is to allow
the Lisp system to use raw list surgery etc. if it happens to be more
effective, regardless of the side-effects to possible other places
pointing to the list. The implementation is free to clobber the list
whichever way it likes, there is no guarantee on the shape of the
contents afterwards. So, the destructive versions should be used
strictly for the results, not for side-effects.

--
From: Hartmann Schaffer
Subject: Re: confused about delete
Date: 
Message-ID: <slrn9c28er.oci.hs@paradise.nirvananet>
In article <··············@artipc5.vub.ac.be>, Joachim De Beule wrote:
>
>Hi all,
>
>I am a bit confused by the effect of the lisp function DELETE.
>It is supposed to be the destructive version of REMOVE but if you
>DELETE the first element of a list, the list is not destructively
>modified:

yes it is, but in this case it doesn't result in any alteration of memory.

pretty much any lisp introduction i have seen contains a section where lists
are explained with these box-and-arrow diagrams.  go through your example
with one of those and remember that unused memory doesn't get removed until
the garbage collector finds reason to do so (i.e. until the-list or anything
else stops pointing to a), and you will understand why your code behaves like
this

>   (setf the-list '(a b c))
>   => (a b c)
>   (delete the-list 'a '(a b c))
>   => (b c)
>   the-list
>   => (a b c)
>
>Two Questions (number 2 more important):
>
>1) Why is this the case?  (I can imagine it is difficult to get rid of
>   the first cons cel of a list without losing the list itself but
>   shouldn't DELETE take care of this anyway and help avoid people like me
>   debugging for quite some time, getting frustrated because
>   they don't understand what goes wrong?)

well, as far as the list itself is concerned, a *has disappeared*.  it is
not the lists fault that there still is a reference to a hanging around
somewhere.  what delete does is a signal to the programmer that if he has
a reference to the original list lying around somewhere, what he accesses
from there *might* change once delete is done.

>2) What is the sollution? Should I allways write something like
>   
>   (setf the-list (delete 'a the-list))

correct

>   to cope with having to delete the first element? Then what is the
>   point of having a destructive version of remove anyway?

the alternative (remove) copies the whole list except for the item to be
deleted, which can be quite time consuming.  if you are sure that you don't
need the original list, delete can be quite a time saver

hs
From: Shannon Spires
Subject: Re: confused about delete
Date: 
Message-ID: <svspire-E36C5B.20100906042001@news.nmia.com>
In article <··············@artipc5.vub.ac.be>, Joachim De Beule 
<·······@arti.vub.ac.be> wrote:

> Hi all,
> 
> I am a bit confused by the effect of the lisp function DELETE.
> It is supposed to be the destructive version of REMOVE but if you
> DELETE the first element of a list, the list is not destructively
> modified:
> ...
> 
> 2) What is the sollution? Should I allways write something like
>    
>    (setf the-list (delete 'a the-list))
> 
>    to cope with having to delete the first element? Then what is the
>    point of having a destructive version of remove anyway?
>    
> Regards and thanks, Joachim

This issue is addressed in the Common Lisp FAQ: 
http://www.cs.cmu.edu/Web/Groups/AI/html/faqs/lang/lisp/part3/faq-doc-4. 
html

The point of #'delete is NOT that it has an easier calling syntax than 
#'remove, but that it is potentially more memory-efficient. One should 
always use SETF in front of #'delete if one would have used SETF in 
front of #'remove, for example.

Here are two interpretations of how to use #'delete. The first is more 
common with beginners, and is wrong:

  WRONG: Call #'delete with lazier syntax than #'remove because it has a 
nifty side effect.

  RIGHT: Call #'delete with the same syntax as #'remove but beware of 
its nasty side effect.

The only trustworthy result from #'delete is the value it returns, not 
the value it changes. This despite the fact that lazy use of #'delete 
will frequently appear to work, which is why it fools so many people. 
You have (fortunately) run into the most common case where lazy use 
fails--deleting the first element of a list.

All that having been said, it is possible to naively write something 
like #'delete which is purely side-effecting--even on the first element 
of a list--without being a macro. Such a function could simply modify 
the CAR of the first cons cell to be that of the second cons cell, and 
stitch around the second. It is not advisable to write such a function 
because it has troublesome failure modes. What happens when you hand it 
a single-cons list, for example? A pure side-effector that works in all
cases has to be a macro, which #'delete is not.

Shannon Spires
·······@nmia.com