On Jan 31, 3:06 am, Jeffrey Straszheim <[email protected]>
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
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
