Subject: Re: problem with delete
From: Erik Naggum <erik@naggum.net>
Date: 2000/10/06
Newsgroups: comp.lang.lisp
Message-ID: <3179815096735973@naggum.net>

* tar@sevak.isi.edu (Thomas A. Russ)
| OK, here's the structure sharing remove for lists.  I won't attempt it
| for non-list sequences.  The only nastiness is that anytime a copy needs
| to be made, the copied part is traversed 3 times. (See ;; ***)

  The non-sharing remove only copies the not-to-be-removed elements,
  like, once:

(defun normal-remove (item list)
  (loop for elt in list
        unless (eq item elt)
        collect elt))

  Incidentally, since you're looking at sharing only some tail of the
  list, you could reverse the list, scan for the first match, reverse
  the part you had traversed, and copy the rest of the list, sans
  matches.  This would avoid any but the final copy.  A deeply
  recursive function could maintain a global variable that would allow
  it to share structure on the way back.

  All in all, I think the simplicity in implementation of a remove
  that copies is much to be preferred over the speed penalty for the
  version that tries to share.  Another useful tidbit here is that if
  you're using a generational garbage collector, mixing and matching
  old and young generations usually has costs

#:Erik
-- 
  If this is not what you expected, please alter your expectations.