Working with zippers and trees

[dabd]

I am trying to work with a tree representation using vectors where the first element is the node value and the rest are the children as suggested here:

http://grokbase.com/t/gg/clojure/12afy2cz9p/how-to-represent-trees-for-use-with-zippers

However I am having trouble using clojure.zip/edit to change a simple tree. I'd like to multiply the odd numbers by 2 in this case.

https://gist.github.com/dabd/7666778

It looks like after editing the first (branch) node clojure.zip/next will get to the end of the tree.

How can I correct this code?

Thanks.

[martin_clausen]

With a nested vector tree you can use the built in vector-zip function to create your zipper.

As to the editing, the source code contains a very similar use-case, which can be adapted to something like the following:

(let [vz (vector-zip [1 2 [3 4 5]])]

        (loop [loc vz]

          (if (end? loc)

            (root loc)

            (recur (next (if (and (integer? (node loc)) (odd? (node loc)))

                   (replace loc (* 2 (node loc)))

                   loc))))))

> [2 2 [6 4 10]]

[dabd]

The built-in vector-zip will build a tree with a different structure than what I need.

I want build a tree as described in the first post: the node value is the first element of the vector and the children the rest of the elements.

zipper.core>  (loop [loc (tree-zipper [1 2 [3 4 5]])]

(if (z/end? loc)

 (z/root loc)

 (do (println (z/node loc))

     (recur (z/next loc)))))

[1 2 [3 4 5]]

2

[3 4 5]

4

5

[1 2 [3 4 5]]

zipper.core>  (loop [loc (z/vector-zip [1 2 [3 4 5]])]

(if (z/end? loc)

 (z/root loc)

 (do (println (z/node loc))

     (recur (z/next loc)))))

[1 2 [3 4 5]]

1

2

[3 4 5]

3

4

5

[1 2 [3 4 5]]

[martin_clausen]

To use the zipper library you have to be able to provide branch? children and make-node functions that apply to your data structure.

I don't see a way to provide a meaningful branch? or children function for the structure you describe. Vector? will not work as branch? as it will not return true if passed the first element in a vector, and next will not work as it will not return the children if passed the first element of a vector.

It looks to me like you don't get past the first element because the call to z/next fails both (and (branch? loc) (down loc)), (right loc) and (up loc) and therefore marks the first element as the end of the of the structure.

Is there a compelling reason for not using the vector-zip structure for your specific use-case?

[dabd]

I'm not sure what you mean by not being able to provide a meaningful branch?.

I would like to represent a tree such a this:

                                  1

                  / \
                 2   3
                    / \
                   4   5

How can I achieve this using zippers?

[Carlo Zancanaro]

On Tue, Nov 26, 2013 at 08:30:15PM -0800, martin_clausen wrote:
> To use the zipper library you have to be able to provide branch? children
> and make-node functions that apply to your data structure.
>
> I don't see a way to provide a meaningful branch? or children function for
> the structure you describe. Vector? will not work as branch? as it will not
> return true if passed the first element in a vector, and next will not work
> as it will not return the children if passed the first element of a vector.

We can write our own functions, though:

(defn children? [n]
(and (vector? n) (next n)))

(defn make-node [n children]
(vec (cons (first n) children)))

(defn tree-zipper [v]
(z/zipper children? next make-node v))

Dario: I tried this with your gist, and the code in your previous email,
and as far as I could tell it worked, so I hope that helps!

Carlo

[Carlo Zancanaro]

Okay, now after actually reading the documentation I can come back with
an actually correct response!

You should only have to change one function:

> (defn make-node [n children]
> (vec (cons (first n) children)))

Your issue was that your original `make-node` function didn't return a
vector, it returned a ConsCell (with a vector as its tail). This meant
that your new node no longer returned true for "children", that is it
identified itself as a leaf.

By making `make-node` return a vector (vec turns any sequable thing into
a vector) your `make-node` now returns a valid branch node, so z/next
behaves as you want it to.

Carlo

[dabd]

Thanks. Do you think the call to z/edit in my code could be simplified? To edit a branch node I have to use conj to build a node only to pass it to make-node which will break it apart again.

[Martin Clausen]

Yes, for instance like this:

(let [vz (z/vector-zip [1 [2] [3 [4 5]]])]
(loop [loc vz]

(if (z/end? loc)
(z/root loc)

(recur (z/next (if (and (integer? (z/node loc)) (odd? (z/node loc)))
(z/replace loc (* 2 (z/node loc)))
loc))))))

Which lets you avoid writing half the infrastructure yourself.

> --
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your
> first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
> ---
> You received this message because you are subscribed to a topic in the
> Google Groups "Clojure" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/d/topic/clojure/ZTWo5gzOx08/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to
> clojure+u...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.

[dabd]

The problem is that your vector-zip is not representing the tree I pictured.

[Martin Clausen]

Ah, sorry. You could use a map-tree instead. It is a bit more verbose,
but I believe it does what you want.

(defn map-tree [root]
(z/zipper
map?
#(seq (:cs %))
(fn [node children]
(assoc node :cs (and children (apply vector children))))
root))

(let [mt (map-tree {:v 1 :cs [{:v 2} {:v 3 :cs [{:v 4} {:v 5}]}]})]
(loop [loc mt]

(if (z/end? loc)
(z/root loc)

(recur (z/next (let [n (:v (z/node loc))]
(if (and (integer? n) (odd? n))
(z/replace loc {:v(* 2 (:v (z/node loc))) :cs
(z/children loc)})
loc)))))))

[dabd]

Your map-tree is exactly like an xml-zip.

The problem I find with it is that now branch? also returns true for leaf nodes:

(def m (map-tree {:v 1 :cs [{:v 2} {:v 3 :cs [{:v 4} {:v 5}]}]}))

> (-> m z/down)

[{:v 2} {:l [], :pnodes [{:v 1, :cs [{:v 2} {:v 3, :cs [{:v 4} {:v 5}]}]}], :ppath nil, :r ({:v 3, :cs [{:v 4} {:v 5}]})}]

> (-> m z/down z/branch?)

true

(def t (tree-zip [1 2 [3 4 5]]))

> (-> t z/down z/branch?)

false

[Martin Clausen]

You are right, but why is this a problem? The zipper works as intended
and if you need to detect leaf nodes, that kan be done by checking for
the presence of a non-empty value of the children key.

[dabd]

Shouldn't be a practical problem just wondering if it's correct given the zipper definition requirements.