Hoy to copy a struct that represents a tree.
in [Lisp]
|
Prev: Reader ?
Next: translating cmucl command line to sbcl
From: Zaka on 22 Oct 2009 11:09 Hello all, I'm trying to do one exercise from Paul Graham's "Ansi Common Lisp": The thing is that I don't know if I'm mistaken in the copy (the function called real-copy-my-tree) or in the comparison ( the function called my-tree- equal). Sorry for the big amount of code, most of it is the tree definition (pretty tedious). Thanks all for your help. Zaka. ;; Exercise 3 ;; Define a structure to represent a tree where each node contains ;; some data and has up to three children. Define: ;; (a) a function to copy such a tree (so that no node in the copy ;; is eql to a node in the original) (defstruct my-tree (elt 0) (l nil) (c nil) (r nil)) ;; Trying to copy a tree: (defun real-copy-my-tree (tree) (if (null tree) nil (make-my-tree :elt (my-tree-elt tree) :l (real-copy-my-tree (my-tree-l tree)) :c (real-copy-my-tree (my-tree-c tree)) :r (real-copy-my-tree (my-tree-r tree))))) ;; Lets represent as a structure the next tree: ;; A don't know an easier way to do it. ;; _________1_________ ;; ______2___ ___3___ ____4_____ ;; 4 5 6 7 8 9 10 11 12 (defparameter tree (make-my-tree :elt '(a))) (setf (my-tree-l tree) (make-my-tree :elt '(b))) (setf (my-tree-c tree) (make-my-tree :elt '(c))) (setf (my-tree-r tree) (make-my-tree :elt '(d))) (setf (my-tree-l (my-tree-l tree)) (make-my-tree :elt '(e))) (setf (my-tree-c (my-tree-l tree)) (make-my-tree :elt '(f))) (setf (my-tree-r (my-tree-l tree)) (make-my-tree :elt '(g))) (setf (my-tree-l (my-tree-c tree)) (make-my-tree :elt '(h))) (setf (my-tree-c (my-tree-c tree)) (make-my-tree :elt '(i))) (setf (my-tree-r (my-tree-c tree)) (make-my-tree :elt '(j))) (setf (my-tree-l (my-tree-r tree)) (make-my-tree :elt '(k))) (setf (my-tree-c (my-tree-r tree)) (make-my-tree :elt '(l))) (setf (my-tree-r (my-tree-r tree)) (make-my-tree :elt '(m))) (defparameter new-tree (copy-my-tree tree)) (defun my-tree-equal (t1 t2) (cond ((and (null t1) (null t2)) t) ((and (eql (my-tree-elt t1) (my-tree-elt t2)) (my-tree-equal (my-tree-l t1) (my-tree-l t2)) (my-tree-equal (my-tree-c t1) (my-tree-c t2)) (my-tree-equal (my-tree-r t1) (my-tree-r t2))) t) (t nil))) (if (my-tree-equal tree new-tree) (print "They're equal.") (print "They're not equal."))
From: Pascal J. Bourguignon on 22 Oct 2009 13:04 Zaka <shanatorio(a)gmail.com> writes: > Hello all, > > I'm trying to do one exercise from Paul Graham's "Ansi Common Lisp": > > The thing is that I don't know if I'm mistaken in the copy (the > function called > real-copy-my-tree) or in the comparison ( the function called my-tree- > equal). > > Sorry for the big amount of code, most of it is the tree definition > (pretty > tedious). > > Thanks all for your help. > > Zaka. > > ;; Exercise 3 > > ;; Define a structure to represent a tree where each node contains > ;; some data and has up to three children. Define: > > ;; (a) a function to copy such a tree (so that no node in the copy > ;; is eql to a node in the original) > > (defstruct my-tree > (elt 0) > (l nil) > (c nil) > (r nil)) I would use words for field names: label, left, center, right, or value, first, second, third, etc. > ;; Trying to copy a tree: > > (defun real-copy-my-tree (tree) > (if (null tree) > nil > (make-my-tree :elt (my-tree-elt tree) > :l (real-copy-my-tree (my-tree-l tree)) > :c (real-copy-my-tree (my-tree-c tree)) > :r (real-copy-my-tree (my-tree-r tree))))) This is correct. > ;; Lets represent as a structure the next tree: > > ;; A don't know an easier way to do it. > > ;; _________1_________ > ;; ______2___ ___3___ ____4_____ > ;; 4 5 6 7 8 9 10 11 12 > > (defparameter tree (make-my-tree :elt '(a))) > > (setf (my-tree-l tree) (make-my-tree :elt '(b))) > (setf (my-tree-c tree) (make-my-tree :elt '(c))) > (setf (my-tree-r tree) (make-my-tree :elt '(d))) > > (setf (my-tree-l (my-tree-l tree)) (make-my-tree :elt '(e))) > (setf (my-tree-c (my-tree-l tree)) (make-my-tree :elt '(f))) > (setf (my-tree-r (my-tree-l tree)) (make-my-tree :elt '(g))) > > (setf (my-tree-l (my-tree-c tree)) (make-my-tree :elt '(h))) > (setf (my-tree-c (my-tree-c tree)) (make-my-tree :elt '(i))) > (setf (my-tree-r (my-tree-c tree)) (make-my-tree :elt '(j))) > > (setf (my-tree-l (my-tree-r tree)) (make-my-tree :elt '(k))) > (setf (my-tree-c (my-tree-r tree)) (make-my-tree :elt '(l))) > (setf (my-tree-r (my-tree-r tree)) (make-my-tree :elt '(m))) Why are your elt lists? Do you really need lists there? Wouldn't mere symbols be what you need? Or numbers, since that's what you show in the diagram above... One way would be to build it from the leaves: (defparameter *tree* ; ALWAYS use *...* for defvar and defparameter (make-my-tree :elt 1 :l (make-my-tree :elt 2 :l (make-my-tree :elt 4) :c (make-my-tree :elt 5) :r (make-my-tree :elt 6)) :c (make-my-tree :elt 3 :l (make-my-tree :elt 7) :c (make-my-tree :elt 8) :r (make-my-tree :elt 9)) :r (make-my-tree :elt 4 :l (make-my-tree :elt 10) :c (make-my-tree :elt 11) :r (make-my-tree :elt 12)))) If this is still too much, you may design a literal for for ternary trees, and write an interpreter to convert the literal data into a my-tree. For example, we could write a ternary tree node as a list containing the label, the left child, the middle, and the right child: (label left middle right) Trailing empty subtree may be omited, so (label left) == (make-my-tree :elt label :l left) We would also simplify the literal form by allowing a leaf to be replaced by its label if it's not a cons cell: label == (label nil nil nil) = (make-my-tree :elt label) So the above tree can be written: (1 (2 (4) (5) (6)) (3 (7 nil nil nil) (8 nil nil nil) (9 nil nil nil)) (4 10 11 12)) or just: (1 (2 4 5 6) (3 7 8 9) (4 10 11 12)) (defun literal-my-tree (sexp) (cond ((null sexp) ; empty tree. nil) ((atom sexp) ; a label for a leaf: (make-my-tree :elt sexp)) (t ; a node (make-my-tree :elt (first sexp) :l (literal-my-tree (second sexp)) :c (literal-my-tree (third sexp)) :r (literal-my-tree (fourth sexp)))))) (defparameter *tree* (literal-my-tree '(1 (2 4 5 6) (3 7 8 9) (4 10 11 12)))) Then if you have a lot of literal my-trees in your program you can even add a reader macro like: {1 (2 4 5 6) (3 7 8 9) (4 10 11 12)} or a dispatching reader macro like: #T(1 (2 4 5 6) (3 7 8 9) (4 10 11 12)) > (defparameter new-tree (copy-my-tree tree)) You're not using your real-copy-my-tree, but the defstruct provided one. I should say that instead of defining a real-copy-my-tree, you might have used the copy-my-tree name, either redefining it, or more prudently, by having defstruct use another name or not define the copier at all: (defstruct (my-tree (:copier nil)) elt l c r) But in any case, even a shallow copy will be my-tree-equal. > (defun my-tree-equal (t1 t2) > (cond > ((and (null t1) (null t2)) t) > ((and (eql (my-tree-elt t1) (my-tree-elt t2)) > (my-tree-equal (my-tree-l t1) (my-tree-l t2)) > (my-tree-equal (my-tree-c t1) (my-tree-c t2)) > (my-tree-equal (my-tree-r t1) (my-tree-r t2))) > t) > (t nil))) This is almost correct. It will break on: (my-tree-equal (make-my-tree :elt 1) nil) I would write it as: (defun my-tree-equal-p (t1 t2) (or (and (null t1) (null t2)) (and t1 t2 (eql (my-tree-elt t1) (my-tree-elt t2)) (my-tree-equal-p (my-tree-l t1) (my-tree-l t2)) (my-tree-equal-p (my-tree-c t1) (my-tree-c t2)) (my-tree-equal-p (my-tree-r t1) (my-tree-r t2))))) but it's the same. > (if (my-tree-equal tree new-tree) > (print "They're equal.") > (print "They're not equal.")) C/USER[231]> (MY-TREE-EQUAL *tree* (copy-my-tree *tree*)) T C/USER[232]> (MY-TREE-EQUAL *tree* (real-copy-my-tree *tree*)) T C/USER[233]> So, what's the problem? -- __Pascal Bourguignon__
From: Zaka on 22 Oct 2009 19:03 Hello Pascal, Thanks for all your grate answers. > Why are your elt lists? Do you really need lists there? Wouldn't > mere symbols be what you need? Or numbers, since that's what you show > in the diagram above... The elements are lists cause I was proving different types of variables and watching the behavior of my application. > You're not using your real-copy-my-tree, but the defstruct provided > one. > > I should say that instead of defining a real-copy-my-tree, you might > have used the copy-my-tree name, either redefining it, or more > prudently, by having defstruct use another name or not define the > copier at all: I used both the automatically created copy-my-tree and mine, and no one worked as desired. > So, what's the problem? As the exercise said, "no node in the copy is eql to a node in the original". So (I thought) it would go like this: > (MY-TREE-EQUAL *tree* (real-copy-my-tree *tree*)) NIL Thanks again. And I hope that time I have explained myself correctly (I'm a youngster). Sincerely, Zaka
From: Kaz Kylheku on 22 Oct 2009 19:37 On 2009-10-22, Zaka <shanatorio(a)gmail.com> wrote: > Hello all, > > I'm trying to do one exercise from Paul Graham's "Ansi Common Lisp": > > The thing is that I don't know if I'm mistaken in the copy (the > function called > real-copy-my-tree) or in the comparison ( the function called my-tree- > equal). > > Sorry for the big amount of code, most of it is the tree definition > (pretty > tedious). > > Thanks all for your help. > > Zaka. > > ;; Exercise 3 > > ;; Define a structure to represent a tree where each node contains > ;; some data and has up to three children. Define: > > ;; (a) a function to copy such a tree (so that no node in the copy > ;; is eql to a node in the original) > > (defstruct my-tree > (elt 0) > (l nil) > (c nil) > (r nil)) This is a pointless thing to do in Lisp, because we can just use conses to do this job. So it boils down to a space-saving optimization. (defun make-tree (elt &rest children) `(,elt ,@children)) Now just use COPY-TREE to copy the tree. > ;; Lets represent as a structure the next tree: > > ;; A don't know an easier way to do it. > > ;; _________1_________ > ;; ______2___ ___3___ ____4_____ > ;; 4 5 6 7 8 9 10 11 12 > > (defparameter tree (make-my-tree :elt '(a))) > > (setf (my-tree-l tree) (make-my-tree :elt '(b))) > (setf (my-tree-c tree) (make-my-tree :elt '(c))) > (setf (my-tree-r tree) (make-my-tree :elt '(d))) > > (setf (my-tree-l (my-tree-l tree)) (make-my-tree :elt '(e))) > (setf (my-tree-c (my-tree-l tree)) (make-my-tree :elt '(f))) > (setf (my-tree-r (my-tree-l tree)) (make-my-tree :elt '(g))) > > (setf (my-tree-l (my-tree-c tree)) (make-my-tree :elt '(h))) > (setf (my-tree-c (my-tree-c tree)) (make-my-tree :elt '(i))) > (setf (my-tree-r (my-tree-c tree)) (make-my-tree :elt '(j))) > > (setf (my-tree-l (my-tree-r tree)) (make-my-tree :elt '(k))) > (setf (my-tree-c (my-tree-r tree)) (make-my-tree :elt '(l))) > (setf (my-tree-r (my-tree-r tree)) (make-my-tree :elt '(m))) You can construct this in one big expression: (make-my-tree :elt 1 :l (make-my-tree :elt 2 :l 4 :c 5 :r 6) :c (make-my-tree :elt 3 :l 7 :c 8 :r 9) :r (make-my-tree :elt 3 :l 10 :c 11 :r 12)) -> #S(MY-TREE :ELT 1 :L #S(MY-TREE :ELT 2 :L 4 :C 5 :R 6) :C #S(MY-TREE :ELT 3 :L 7 :C 8 :R 9) :R NIL) If you use lists to represent n-ary trees, like they were meant to, then it's just: (1 (2 4 5 6) (3 7 8 9) (4 10 11 12)) You can write code to generate a tree from the above, so you can do: (make-my-tree-from-list '(1 (2 4 5 6) (3 7 8 9) (4 10 11 12))) I.e. even if we decide to use structs for the internal representation, it helps us to be able to serialize and deserialize the tree to and from the simple list representation. (defun zippend (list1 list2) (mapcan #'list list1 list2)) (defun make-my-tree-from-list (list) (if (atom list) list (destructuring-bind (elt . children) list (let ((child-trees (mapcar #'make-my-tree-from-list children))) (apply #'make-my-tree :elt elt (zippend '(:l :c :r) child-trees))))))
From: Pascal J. Bourguignon on 22 Oct 2009 21:22
Zaka <shanatorio(a)gmail.com> writes: > Hello Pascal, > > Thanks for all your grate answers. > >> Why are your elt lists? �Do you really need lists there? �Wouldn't >> mere symbols be what you need? �Or numbers, since that's what you show >> in the diagram above... > > The elements are lists cause I was proving different types of > variables and watching the behavior of my application. > >> You're not using your real-copy-my-tree, but the defstruct provided >> one. >> >> I should say that instead of defining a real-copy-my-tree, you might >> have used the copy-my-tree name, either redefining it, or more >> prudently, by having defstruct use another name or not define the >> copier at all: > > I used both the automatically created copy-my-tree and mine, and no > one worked as desired. > >> So, what's the problem? > > As the exercise said, "no node in the copy is eql to a node in the > original". > > So (I thought) it would go like this: > >> (MY-TREE-EQUAL *tree* (real-copy-my-tree *tree*)) > NIL > > Thanks again. > > And I hope that time I have explained myself correctly (I'm a > youngster). The my-tree-equal-p predicate and the post-condition of real-copy-my-tree are not the same thing. To check the assertion that "no node in the copy is eql to a node in the original" you will need to collect all the nodes of a tree in a set, and compute the intersection. (defun |no node in the copy is eql to a node in the original| (copy original) (null (intersection (collect-nodes copy) (collect-nodes original)))) ;; (this work because INTERSECTION, like most functions in CL, use EQL as test function). ;; we could also explicitely pass a test: ;; (intersection (collect-nodes copy) (collect-nodes original) :test (function eql)) (defun collect-nodes (tree) (if (null tree) '() (cons tree (append (collect-nodes (my-tree-l tree)) (collect-nodes (my-tree-c tree)) (collect-nodes (my-tree-r tree)))))) Then you can see the difference between the deep copy and the shallow copy: C/USER[245]> (|no node in the copy is eql to a node in the original| *tree* (real-copy-my-tree *tree*)) T C/USER[246]> (|no node in the copy is eql to a node in the original| *tree* (copy-my-tree *tree*)) NIL To see what nodes are unique amongst the original and the copy, you can just include both node collections in the same list, binding *print-circle* to true so that the lisp printer unifies the unique nodes: C/USER[247]> (setf *print-circle* t) T C/USER[248]> (list (collect-nodes *tree*) (collect-nodes (copy-my-tree *tree*))) ((#S(MY-TREE :ELT 1 :L #1=#S(MY-TREE :ELT 2 :L #2=#S(MY-TREE :ELT 4 :L NIL :C NIL :R NIL) :C #3=#S(MY-TREE :ELT 5 :L NIL :C NIL :R NIL) :R #4=#S(MY-TREE :ELT 6 :L NIL :C NIL :R NIL)) :C #5=#S(MY-TREE :ELT 3 :L #6=#S(MY-TREE :ELT 7 :L NIL :C NIL :R NIL) :C #7=#S(MY-TREE :ELT 8 :L NIL :C NIL :R NIL) :R #8=#S(MY-TREE :ELT 9 :L NIL :C NIL :R NIL)) :R #9=#S(MY-TREE :ELT 4 :L #10=#S(MY-TREE :ELT 10 :L NIL :C NIL :R NIL) :C #11=#S(MY-TREE :ELT 11 :L NIL :C NIL :R NIL) :R #12=#S(MY-TREE :ELT 12 :L NIL :C NIL :R NIL))) #1# #2# #3# #4# #5# #6# #7# #8# #9# #10# #11# #12#) (#S(MY-TREE :ELT 1 :L #1# :C #5# :R #9#) #1# #2# #3# #4# #5# #6# #7# #8# #9# #10# #11# #12#)) So in addition to all the nodes numbered from #1# to #12# and that are all used in both the original and the shallow copy, there are two unique nodes, the original one, and the shallow copy returned by copy-my-tree. Contrarily to the deep copy, in which all the nodes are duplicated: C/USER[249]> (list (collect-nodes *tree*) (collect-nodes (real-copy-my-tree *tree*))) ((#S(MY-TREE :ELT 1 :L #1=#S(MY-TREE :ELT 2 :L #2=#S(MY-TREE :ELT 4 :L NIL :C NIL :R NIL) :C #3=#S(MY-TREE :ELT 5 :L NIL :C NIL :R NIL) :R #4=#S(MY-TREE :ELT 6 :L NIL :C NIL :R NIL)) :C #5=#S(MY-TREE :ELT 3 :L #6=#S(MY-TREE :ELT 7 :L NIL :C NIL :R NIL) :C #7=#S(MY-TREE :ELT 8 :L NIL :C NIL :R NIL) :R #8=#S(MY-TREE :ELT 9 :L NIL :C NIL :R NIL)) :R #9=#S(MY-TREE :ELT 4 :L #10=#S(MY-TREE :ELT 10 :L NIL :C NIL :R NIL) :C #11=#S(MY-TREE :ELT 11 :L NIL :C NIL :R NIL) :R #12=#S(MY-TREE :ELT 12 :L NIL :C NIL :R NIL))) #1# #2# #3# #4# #5# #6# #7# #8# #9# #10# #11# #12#) (#S(MY-TREE :ELT 1 :L #13=#S(MY-TREE :ELT 2 :L #14=#S(MY-TREE :ELT 4 :L NIL :C NIL :R NIL) :C #15=#S(MY-TREE :ELT 5 :L NIL :C NIL :R NIL) :R #16=#S(MY-TREE :ELT 6 :L NIL :C NIL :R NIL)) :C #17=#S(MY-TREE :ELT 3 :L #18=#S(MY-TREE :ELT 7 :L NIL :C NIL :R NIL) :C #19=#S(MY-TREE :ELT 8 :L NIL :C NIL :R NIL) :R #20=#S(MY-TREE :ELT 9 :L NIL :C NIL :R NIL)) :R #21=#S(MY-TREE :ELT 4 :L #22=#S(MY-TREE :ELT 10 :L NIL :C NIL :R NIL) :C #23=#S(MY-TREE :ELT 11 :L NIL :C NIL :R NIL) :R #24=#S(MY-TREE :ELT 12 :L NIL :C NIL :R NIL))) #13# #14# #15# #16# #17# #18# #19# #20# #21# #22# #23# #24#)) -- __Pascal Bourguignon__ |