Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!think.com!snorkelwacker.mit.edu!bloom-beacon!eru!hagbard!sunic!liuida!isy!lysator.liu.se!bellman
From: bellman@lysator.liu.se (Thomas Bellman)
Newsgroups: comp.lang.lisp
Subject: Re: Destructive Operations
Message-ID: <595@lysator.liu.se>
Date: 26 Apr 91 01:41:07 GMT
References: <1351@ai.cs.utexas.edu> <1991Apr25.052624.14541@Think.COM>
Sender: news@isy.liu.se (Lord of the News)
Organization: Lysator Computer Club, Linkoping University, Sweden
Lines: 46

In article <1991Apr25.052624.14541@Think.COM> Barry Margolin
(barmar@think.com) writes:

> 1. Forgetting to store the result back.  Even though the list is modified
> in place, it is still necessary to store the result back into the original
> location, e.g.

>	 (setq foo (delete 'x foo))

> This is necessary because X might be the first element of the list, so
> DELETE could just return (CDR FOO), without actually modifying anything (it
> can't store the result itself because of Lisp's call-by-value semantics).

Well, I don't know very much about CommonLisp, but in good ol'
InterLISP, there was a function called DREMOVE, which did *not*
require the user to store the result back, *even* if it had to remove
the first element.  It is easy to remove the first element of a list.

	(DL REM1ST (L) (RPLACD (RPLACA L (CADR L)) (CDDR L)))

to speak InterLISP.  (DL is the same as defun in CommonLisp.)

The only catch with DREMOVE was if the result was NIL.  Then it
couldn't store the result back.  If the result should be NIL, then
DREMOVE didn't modify the original list at all.  (It returned NIL,
though.)

But then of course, there are some tricks you can use to make it
possible to turn a non-empty list into an empty list.  You have to
have some structure around your lists, but that shouldn't be any
problem.

Personally, I like the TCONC type of lists, where you pass around a
cons cell whith the car pointing to the actual list, and the cdr
pointing to the last cons cell of the list.  That way, it is very
cheap to add elements at the end of a list, and you can destructively
remove elements from the list.  (It isn't inexpensive to remove the
last element of the list, but it is definitely possible to do "purely"
destructive functions.  I know of no scheme where it is cheap for all
elements of the list.)


--
Thomas Bellman,  Lysator Computer Club   !  "Make Love - Nicht Wahr"
          Linkoping University, Sweden   !  "Too much of a good thing is
e-mail:         Bellman@Lysator.LiU.Se   !   WONDERFUL."     -- Mae West