when copy-list or copy-tree are not deep enough?
I have a big list and I need a function that returns one of its
branches depending on condition.
Later on, in another function I use that branch and modify it
(appending other lists to it).
Now, even though I return that branch using copy-tree, still when I
modify that branch, it modifies the original tree.
Is it because copy-tree only copies conses but not the atoms
themselves?
How can I do a deep copy of the list so it creates a completely new
instance of that branch?
Thank you,
Andrew
On Apr 29, 12:30 pm, Trastabuga <·········@gmail.com> wrote:
> when copy-list or copy-tree are not deep enough?
copy-tree is deeper than copy-list.
Copy-list will copy the list structure, but use the same elements (CAR-
s) regardless of whether they are themselves conses or atoms.
Copy-tree will copy all of the conses (which are transitively
reachable by navigating CAR and CDR from the root cons). But anything
which is not a CONS is not copied.
So for instance if you have a tree full of structs, copy-tree will not
make copies of those structs; they are shared between the new tree and
old. Structs are atoms, and copy-tree copies only conses.
So the answer is that if copy-tree is not deep enough, then copy-list
is not deep enough. And copy-tree is not deep enough whenever it's
insufficient to just copy the tree structure, without actually copying
the atoms.
The predicate ``deep enough'' can only be evaluated with respect to
your program's requirements.
> I have a big list and I need a function that returns one of its
> branches depending on condition.
> Later on, in another function I use that branch and modify it
> (appending other lists to it).
To mutually isolate copies of a list from the effects of destructive
append operations done on any of the copies, copy-list is good enough.
To mutually isolate copies of a tree from any destructive tree
structure manipulation, copy-tree is good enough.
Neither of these will shield the copies from destructive modifications
of the atoms themselves.
> Now, even though I return that branch using copy-tree, still when I
> modify that branch, it modifies the original tree.
That's impossible, unless by ``modify'' you mean that you are changing
the contents of the atoms found at the leaves of the tree.
> Is it because copy-tree only copies conses but not the atoms
> themselves?
> How can I do a deep copy of the list so it creates a completely new
> instance of that branch?
You could perform a COPY-TREE first, followed by a recursive walk of
the newly consed tree structure, in which you replace all mutable
atoms by copies.
This is difficult to do in general, because there is no unified
operation for copying any atom. You could write a generic copy
function and specialize it to the objects you care about in your
program.
Mutable atoms would be things like vectors (and, recursively, the
mutable atoms contained in vectors therein), strings, structs, CLOS
objects. You don't bother with numbers and symbols.
Kaz Kylheku <········@gmail.com> wrote:
+---------------
| Trastabuga <·········@gmail.com> wrote:
| > How can I do a deep copy of the list so it creates a completely new
| > instance of that branch?
|
| You could perform a COPY-TREE first, followed by a recursive walk of
| the newly consed tree structure, in which you replace all mutable
| atoms by copies.
|
| This is difficult to do in general, because there is no unified
| operation for copying any atom. You could write a generic copy
| function and specialize it to the objects you care about in your
| program.
+---------------
But then next week somebody comes up with a new atom that his generic
COPY-ATOM doesn't know about, and he has to invent a new specialization
for it... which is *NOT* trivial, in general. Kent's classic article
on copying & equality goes into some of the reasons why not:
http://www.nhplace.com/kent/PS/EQUAL.html
but the example that does it for me is the case of objects with
internal constraints between their components, e.g., a queue header
which contains a tail pointer that points to the end of the queue, or
a bidirectional queue or doubly-linked list type. Or a general graph
with loops? All of these create problems for a COPY-ATOM operation.
Or what about objects with semantics that are supposed to represent
external objects? Is it fraud when one does (COPY-ATOM BANK-ACCOUNT)?
And if one does (COPY-ATOM AIRLINE-SEAT-RESERVATION), who loses the
resulting game of musical chairs?
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
P� Tue, 29 Apr 2008 21:30:18 +0200, skrev Trastabuga <·········@gmail.com>:
> when copy-list or copy-tree are not deep enough?
> I have a big list and I need a function that returns one of its
> branches depending on condition.
> Later on, in another function I use that branch and modify it
> (appending other lists to it).
> Now, even though I return that branch using copy-tree, still when I
> modify that branch, it modifies the original tree.
> Is it because copy-tree only copies conses but not the atoms
> themselves?
Yes.
> How can I do a deep copy of the list so it creates a completely new
> instance of that branch?
>
> Thank you,
> Andrew
You write your own. copy-seq works like copy-list but works on arrays as
well.
sequencep sais whether it is a sequence. Since a list is also a sequence
you just need a
depth first traversal to duplicate the structure.
Something like:
(defun deep-copy-sequence (sequence)
"Recursivly copy all array's and list's."
(when (subtypep (type-of sequence) 'sequence)
(setf sequence (copy-seq sequence))
(loop for i from 0 below (length sequence) do
(setf (elt sequence i) (deep-copy-sequence (elt sequence i)))))
sequence)
TEST 52 > (defparameter a '(1 2 #(3 4 5 (1 2 3))))
A
TEST 53 > (defparameter b (deep-copy-sequence a))
B
TEST 54 > (setf (second (aref (third b) 3)) #\*)
#\*
TEST 55 > a
(1 2 #(3 4 5 (1 2 3)))
TEST 56 > b
(1 2 #(3 4 5 (1 #\* 3)))
--------------
John Thingstad
P� Tue, 29 Apr 2008 22:26:55 +0200, skrev John Thingstad
<·······@online.no>:
>
> You write your own. copy-seq works like copy-list but works on arrays as
> well.
> sequencep sais whether it is a sequence. Since a list is also a sequence
> you just need a
> depth first traversal to duplicate the structure.
>
Lot of nonsence here. (subtypep (type-of sequence) 'sequence) determines
if it is a sequence.
Traversal is breath first. (Next time I will write the code FIRST.)
> Something like:
>
> (defun deep-copy-sequence (sequence)
> "Recursivly copy all array's and list's."
> (when (subtypep (type-of sequence) 'sequence)
> (setf sequence (copy-seq sequence))
> (loop for i from 0 below (length sequence) do
> (setf (elt sequence i) (deep-copy-sequence (elt sequence
> i)))))
> sequence)
>
Using the iterate package this is a more efficient version.
(defun deep-copy-sequence (sequence)
"Recursivly copy all array's and list's."
(when (subtypep (type-of sequence) 'sequence)
(setf sequence (copy-seq sequence))
(iter (for element in-sequence sequence)
(when (subtypep (type-of element) 'sequence)
(setf element (deep-copy-sequence element)))))
sequence)
1. No need recursivly go down the structure for atoms.
2. elt and length are not needed. Both have order n complexity for list's.
This works for characters, numbers, vectors, strings, arrays
You get in trouble with structures and classes.
They can in themself have substructure.
For your own classes define a method deep-copy.
For library classes/structure all bets are off. You could hack something
together I suppose using introspection..
--------------
John Thingstad
P� Tue, 29 Apr 2008 23:24:00 +0200, skrev John Thingstad
<·······@online.no>:
>>
>> (defun deep-copy-sequence (sequence)
>> "Recursivly copy all array's and list's."
>> (when (subtypep (type-of sequence) 'sequence)
>> (setf sequence (copy-seq sequence))
>> (loop for i from 0 below (length sequence) do
>> (setf (elt sequence i) (deep-copy-sequence (elt sequence
>> i)))))
>> sequence)
>>
Third and final version.. Trades succinctness for efficiency.
Lisp needs a efficient generic iterator over a sequence..
(Looking at the macroexpansion of iter it was just length and elt under
the hood)
(defun deep-copy-sequence (sequence)
"Recursivly copy all array's and list's."
(cond
((arrayp sequence)
(setf sequence (copy-seq sequence))
(loop for element across sequence
when (subtypep (type-of element) 'sequence)
do (setf element (deep-copy-sequence element))))
((listp sequence)
(setf sequence (copy-list sequence))
(loop for element in sequence
when (subtypep (type-of element) 'sequence)
do (setf element (deep-copy-sequence element)))))
sequence)
--------------
John Thingstad
On Apr 29, 2:54 pm, "John Thingstad" <·······@online.no> wrote:
> (defun deep-copy-sequence (sequence)
> "Recursivly copy all array's and list's."
> (cond
> ((arrayp sequence)
> (setf sequence (copy-seq sequence))
ARRAYP matches multidimensional arrays, which are not sequences and
cannot be passed to COPY-SEQ. But it wouldn't be hard to add support
for copying them.
> (loop for element across sequence
> when (subtypep (type-of element) 'sequence)
> do (setf element (deep-copy-sequence element))))
> ((listp sequence)
Since all your COND tests are for type, TYPECASE can be used instead:
(typecase sequence
(vector ...)
(list ...)
...
(otherwise ...))
> (setf sequence (copy-list sequence))
> (loop for element in sequence
> when (subtypep (type-of element) 'sequence)
> do (setf element (deep-copy-sequence element)))))
> sequence)
The problem here is that although the semantics of COPY-TREE are
extended here to cover vector structure as well as cons structure,
nothing is done about atoms at all; they are not replicated.
(defgeneric deep-copy (whatever))
(defmethod deep-copy ((vec vector))
(map 'vector #'deep-copy vec))
(defmethod deep-copy ((cons cons))
(cons (deep-copy (car cons))
(deep-copy (cdr cons))))
;; Note: this is what handles (deep-copy nil) -> nil,
;; if there is no specialization to NULL, since NIL
;; is a kind of symbol.
(defmethod deep-copy ((sym symbol)) sym)
(defmethod deep-copy ((num number)) num)
Now we can add multi-dimensional array support. CLOS should match on
VECTOR more specifically if the array is one dimensional, and pass the
greater than rank 2 ones to this specialization:
(defmethod deep-copy ((array array))
;; exercise for reader
)
We don't have a T specialization, so DEEP-COPY will blow up with a no
applicable method error if it doesn't know how to copy something. E.g.
(deep-copy *random-state*)
For this one, we can just write
(defmethod deep-copy ((rs random-state))
(make-random-state rs))
Etc.
P� Wed, 30 Apr 2008 00:59:58 +0200, skrev Kaz Kylheku <········@gmail.com>:
> On Apr 29, 2:54�pm, "John Thingstad" <·······@online.no> wrote:
>> (defun deep-copy-sequence (sequence)
>> � �"Recursivly copy all array's and list's."
>> � �(cond
>> � � ((arrayp sequence)
>> (setf sequence (copy-seq sequence))
>
> ARRAYP matches multidimensional arrays, which are not sequences and
> cannot be passed to COPY-SEQ. But it wouldn't be hard to add support
> for copying them.
>
>> � � �(loop for element across sequence
>> � � � � � �when (subtypep (type-of element) 'sequence)
>> � � � � � �do (setf element (deep-copy-sequence element))))
>> � � ((listp sequence)
>
> Since all your COND tests are for type, TYPECASE can be used instead:
>
> (typecase sequence
> (vector ...)
> (list ...)
> ...
> (otherwise ...))
>
>
>> � � �(setf sequence (copy-list sequence))
>> � � �(loop for element in sequence
>> � � � � � �when (subtypep (type-of element) 'sequence)
>> � � � � � �do (setf element (deep-copy-sequence element)))))
>> � �sequence)
>
> The problem here is that although the semantics of COPY-TREE are
> extended here to cover vector structure as well as cons structure,
> nothing is done about atoms at all; they are not replicated.
>
> (defgeneric deep-copy (whatever))
>
> (defmethod deep-copy ((vec vector))
> (map 'vector #'deep-copy vec))
>
> (defmethod deep-copy ((cons cons))
> (cons (deep-copy (car cons))
> (deep-copy (cdr cons))))
>
UGH. this is not scheme.
> ;; Note: this is what handles (deep-copy nil) -> nil,
> ;; if there is no specialization to NULL, since NIL
> ;; is a kind of symbol.
> (defmethod deep-copy ((sym symbol)) sym)
>
> (defmethod deep-copy ((num number)) num)
>
> Now we can add multi-dimensional array support. CLOS should match on
> VECTOR more specifically if the array is one dimensional, and pass the
> greater than rank 2 ones to this specialization:
>
> (defmethod deep-copy ((array array))
> ;; exercise for reader
> )
>
> We don't have a T specialization, so DEEP-COPY will blow up with a no
> applicable method error if it doesn't know how to copy something. E.g.
>
> (deep-copy *random-state*)
>
> For this one, we can just write
>
> (defmethod deep-copy ((rs random-state))
> (make-random-state rs))
>
> Etc.
>
>
>
Too complicated..
Indeed inspect uses a approach like you described.
I figure my simple algorithm (the first) covers most cases where you would
want do do this. If it is too slow you should probably find a alternative
to copying anyway. The same is the case if it contains classes and the
like. It is better to let the classes themselves provide a copying scheme.
Let context rule whether shallow-copy deep-copy or structural-copy is
desirable. deep-copy is too blunt and general. If it's need arises it
might be a sign that your design is wrong.
--------------
John Thingstad
P� Wed, 30 Apr 2008 00:59:58 +0200, skrev Kaz Kylheku <········@gmail.com>:
>
> Now we can add multi-dimensional array support. CLOS should match on
> VECTOR more specifically if the array is one dimensional, and pass the
> greater than rank 2 ones to this specialization:
>
> (defmethod deep-copy ((array array))
> ;; exercise for reader
> )
>
Good point! But using row-major-aref rather than aref should work for
multi-dimentional array's too.
You would need to use array-total-size too.
Or a displacement array.
untested.
(loop for index from 0 below (array-total-size sequence)
do (setf (row-major-aref sequence index) (deep-copy (row-major-aref
sequence index)
or
(loop for element across (make-array (array-total-size sequence)
:displaced-to sequence)
do (setf element (deep-copy element)))
--------------
John Thingstad
On Apr 29, 5:54 pm, "John Thingstad" <·······@online.no> wrote:
> På Tue, 29 Apr 2008 23:24:00 +0200, skrev John Thingstad
> <·······@online.no>:
>
>
>
> >> (defun deep-copy-sequence (sequence)
> >> "Recursivly copy all array's and list's."
> >> (when (subtypep (type-of sequence) 'sequence)
> >> (setf sequence (copy-seq sequence))
> >> (loop for i from 0 below (length sequence) do
> >> (setf (elt sequence i) (deep-copy-sequence (elt sequence
> >> i)))))
> >> sequence)
>
> Third and final version.. Trades succinctness for efficiency.
> Lisp needs a efficient generic iterator over a sequence..
> (Looking at the macroexpansion of iter it was just length and elt under
> the hood)
>
> (defun deep-copy-sequence (sequence)
> "Recursivly copy all array's and list's."
> (cond
> ((arrayp sequence)
> (setf sequence (copy-seq sequence))
> (loop for element across sequence
> when (subtypep (type-of element) 'sequence)
> do (setf element (deep-copy-sequence element))))
> ((listp sequence)
> (setf sequence (copy-list sequence))
> (loop for element in sequence
> when (subtypep (type-of element) 'sequence)
> do (setf element (deep-copy-sequence element)))))
> sequence)
>
> --------------
> John Thingstad
John, your original version of deep-copy-sequence works, but the
latest doesn't (the original list gets changed).
I can't put my finger on it, the simple copy-list should work, but the
tree is so complicated so I can't make a simple test and show why the
original list gets mutilated.
Thank you!
Andrew
On Apr 29, 4:46 pm, Trastabuga <·········@gmail.com> wrote:
> On Apr 29, 5:54 pm, "John Thingstad" <·······@online.no> wrote:
> > (defun deep-copy-sequence (sequence)
> > "Recursivly copy all array's and list's."
> > (cond
> > ((arrayp sequence)
> > (setf sequence (copy-seq sequence))
> > (loop for element across sequence
> > when (subtypep (type-of element) 'sequence)
> > do (setf element (deep-copy-sequence element))))
> > ((listp sequence)
> > (setf sequence (copy-list sequence))
> > (loop for element in sequence
> > when (subtypep (type-of element) 'sequence)
> > do (setf element (deep-copy-sequence element)))))
> > sequence)
>
> > --------------
> > John Thingstad
>
> John, your original version of deep-copy-sequence works, but the
> latest doesn't (the original list gets changed).
The problem is that the (SETF ELEMENT ...) expressions in the LOOP-s
don't do what is intended. ELEMENT is a local variable, not a symbol
macro covering the original storage place within the sequence.
P� Wed, 30 Apr 2008 05:19:59 +0200, skrev Kaz Kylheku <········@gmail.com>:
> On Apr 29, 4:46�pm, Trastabuga <·········@gmail.com> wrote:
>> On Apr 29, 5:54 pm, "John Thingstad" <·······@online.no> wrote:
>> > (defun deep-copy-sequence (sequence)
>> > � �"Recursivly copy all array's and list's."
>> > � �(cond
>> > � � ((arrayp sequence)
>> > � � �(setf sequence (copy-seq sequence))
>> > � � �(loop for element across sequence
>> > � � � � � �when (subtypep (type-of element) 'sequence)
>> > � � � � � �do (setf element (deep-copy-sequence element))))
>> > � � ((listp sequence)
>> > � � �(setf sequence (copy-list sequence))
>> > � � �(loop for element in sequence
>> > � � � � � �when (subtypep (type-of element) 'sequence)
>> > � � � � � �do (setf element (deep-copy-sequence element)))))
>> > � �sequence)
>>
>> > --------------
>> > John Thingstad
>>
>> John, your original version of deep-copy-sequence works, but the
>> latest doesn't (the original list gets changed).
>
> The problem is that the (SETF ELEMENT ...) expressions in the LOOP-s
> don't do what is intended. ELEMENT is a local variable, not a symbol
> macro covering the original storage place within the sequence.
DUH! right..
(loop for rest over sequence do (setf (car rest) (deep-copy-sequence (car
rest)))
might fare better.
--------------
John Thingstad
"John Thingstad" <·······@online.no> writes:
> Lot of nonsence here. (subtypep (type-of sequence) 'sequence) determines
> if it is a sequence.
So does the simpler
(typep sequence 'sequence)
--
Thomas A. Russ, USC/Information Sciences Institute