Prev: Reader ?
Next: translating cmucl command line to sbcl
From: Zaka on 22 Oct 2009 22:37
Hello again.

I understood that if "no node in the copy is eql to a node in the
original" it would be enough to compare each element with
the corresponding element of the copied tree.

Now I understand that you must collect all the nodes not only
elements, and that's why you use "(cons (tree..." instead of "(cons
(my-tree-elt tree)..." in collect-nodes.

> (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))))))

It was much easier to do the exercise than prove that it was right (as
usual).

Thanks a lot for your effort, I learn from each one of your messages.

Best regards,

Zaka.
From: Vassil Nikolov on 22 Oct 2009 23:58

On Thu, 22 Oct 2009 23:37:51 +0000 (UTC), Kaz Kylheku <kkylheku(a)gmail.com> said:
> ...
> 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))

E.g. even "for free":

(defstruct (your-tree (:type list)) elt l c r)
=> your-tree
(make-your-tree :elt 1
:l (make-your-tree :elt 2
:l 4
:c 5
:r 6)
:c (make-your-tree :elt 3
:l 7
:c 8
:r 9)
:r (make-your-tree :elt 4
:l 10
:c 11
:r 12))
=> (1 (2 4 5 6) (3 7 8 9) (4 10 11 12))

---Vassil.


--
"Even when the muse is posting on Usenet, Alexander Sergeevich?"
From: Vassil Nikolov on 23 Oct 2009 00:06

On Fri, 23 Oct 2009 03:22:21 +0200, pjb(a)informatimago.com (Pascal J. Bourguignon) said:
> ...
> (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))))))

APPEND?!

---Vassil.


--
"Even when the muse is posting on Usenet, Alexander Sergeevich?"
From: Vassil Nikolov on 23 Oct 2009 00:21

On Thu, 22 Oct 2009 08:09:05 -0700 (PDT), Zaka <shanatorio(a)gmail.com> said:
> ...
> (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)))

By the way, you could also consider

(defun my-tree-equal-without-shared-substructure (t1 t2 &optional (payload-equality-test #'eql))
(cond ((and (null t1) (null t2)) t)
((or (null t1) (null t2) (eql t1 t2)) nil)
((and (funcall payload-equality-test (my-tree-elt t1) (my-tree-elt t2))
(my-tree-equal-without-shared-substructure (my-tree-l t1) (my-tree-l t2) payload-equality-test)
(my-tree-equal-without-shared-substructure (my-tree-c t1) (my-tree-c t2) payload-equality-test)
(my-tree-equal-without-shared-substructure (my-tree-r t1) (my-tree-r t2) payload-equality-test)) t)
(t nil)))

(untested).

---Vassil.


--
"Even when the muse is posting on Usenet, Alexander Sergeevich?"
From: Pascal J. Bourguignon on 23 Oct 2009 00:27
Vassil Nikolov <vnikolov(a)pobox.com> writes:

> On Thu, 22 Oct 2009 23:37:51 +0000 (UTC), Kaz Kylheku <kkylheku(a)gmail.com> said:
>> ...
>> 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))
>
> E.g. even "for free":
>
> (defstruct (your-tree (:type list)) elt l c r)
> => your-tree
> (make-your-tree :elt 1
> :l (make-your-tree :elt 2
> :l 4
> :c 5
> :r 6)
> :c (make-your-tree :elt 3
> :l 7
> :c 8
> :r 9)
> :r (make-your-tree :elt 4
> :l 10
> :c 11
> :r 12))
> => (1 (2 4 5 6) (3 7 8 9) (4 10 11 12))


While using bare lists for random data structures such as tree nodes
is indeed practical for Q&D code and exploratory code, soon enough in
real applications you need a distinct data type such as a real
structure or a class.


However, there's one more step toward this direction, using the :named option:

(defstruct (your-tree (:type list) (:named)) elt l c r)
(defstruct (point (:type list) (:named)) x y)

(make-your-tree :elt 1
:l (make-your-tree :elt (make-point :x 1 :y 2))
:c (make-your-tree :elt (make-point :x 0 :y 0))
:r (make-your-tree :elt (make-point :x 2 :y 1)))
--> (YOUR-TREE 1 (YOUR-TREE (POINT 1 2) NIL NIL NIL)
(YOUR-TREE (POINT 0 0) NIL NIL NIL) (YOUR-TREE (POINT 2 1) NIL NIL NIL))

But these lists cannot be discriminated by generic functions.

--
__Pascal Bourguignon__
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6
Prev: Reader ?
Next: translating cmucl command line to sbcl