That Zipper thing

[Jeffrey Straszheim]

Does anyone know of a gentle introduction to the Zipper stuff, and how
it is used in Clojure?

Thanks in advance.

[James Reeves]

On Jan 31, 3:06 am, Jeffrey Straszheim <straszheimjeff...@gmail.com>
wrote:

> Does anyone know of a gentle introduction to the Zipper stuff, and how
> it is used in Clojure?

My understanding of zippers is that they are a way of efficiently
navigating a tree data structure in a functional manner. So if we have
the tree:

A
/ \
B C
| / \
D E F

Then it's quite easy to navigate down the tree by picking a subtree.
So if we want to go down to C:

C
/ \
E F

But what if we want to go back up? We've lost the reference back to A.
Zippers provide a solution to this; instead of taking a subtree,
zippers change the root of the tree:

C
/|\
E F A
|
B
|
D

The links are still the same, but we've moved the root of the tree to
C. If we want to go to E, we can do that, too:

E
|
C
/ \
F A
|
B
|
D

Thus, zippers enable one to both quickly move up and down a tree in a
way that doesn't involve bi-directional nodes or a mutating "current
node" variable.

In Clojure, using a tree is actually much simpler than the theory.
Let's represent our tree using lists:

user=> (def t '(:a (:b :d) (:c :e :f)))
#'user/t

In order to turn this into a zipper, we need to use the zipper
function. Because we've chosen to use lists to represent our tree,
this is pretty simple:

user=> (require '[clojure.zip :as zip])
nil
user=> (def z (zip/zipper rest rest cons t))
#'user/z

Now we've got our zipper, we can look at the original tree using zip/
node:

user=> (zip/node z)
(:a (:b :d) (:c :e :f))

And we can go down:

=> (def z (zip/down z))
#'user/z
user=> (zip/node z)
(:b :d)

Right:

user=> (def z (zip/right z))
#'user/z
user=> (zip/node z)
(:c :e :f)

And back up again:

user=> (def z (zip/up z))
#'user/z
user=> (zip/node z)
(:a (:b :d) (:c :e :f))

All in a completely functional way.

- James

[Jeffrey Straszheim]

That seems simple enough. Thanks.

[e]

I don't understand this: (def z (zip/zipper rest rest cons t))

Also, it didn't make sense why down arbitrarily brought you to the left child.  Why wouldn't you have to say, "down-left"?

Thanks.

[James Reeves]

In Feb 1, 2:32 am, e <evier...@gmail.com> wrote:
> I don't understand this: (def z (zip/zipper rest rest cons t))

From the API docs on zipper:

(zipper branch? children make-node root)

The branch? predicate is rest, because if a node has children, then
rest will not be nil, and therefore true.

The children predicate is also rest, because that's how the children
are stored.

make-node takes a node and some children, and creates a branch. That's
cons because (cons :c '(:e :f)) is (:c :e :f), which is what we want.

> Also, it didn't make sense why down arbitrarily brought you to the left
> child.  Why wouldn't you have to say, "down-left"?

Because that's how down is defined. Check the docs:

(down loc)
Returns the loc of the leftmost child of the node at this loc

- James