views:

78

answers:

2

I am creating trees of s-expressions for a genetic programming problem, and need to alter parts of the trees during the evolution process. I came across the Clojure zipper function that seems like it should be perfect, but for the life of me I can't figure out how to use it.

For example, say I create a zipper with

(def zipped (zip/seq-zip `(+ (- 1 2) 3)))

I understand this to represent a tree with + at the root, one that looks like this:

   +
 -   3
1 2

My zipper, though, doesn't agree with this: If I ask for the first node with (-> zipped zip/down zip/node) it gives me + (which is correct) but it (-> zipped zip/down zip/down) doesn't take me to -, instead it returns nil. Indeed, (-> zipped zip/down zip/rights) gives the rest of the tree as siblings to the right of the root, which suggests to me that I don't have a tree at all:

user> (-> zipped zip/down zip/rights)
((clojure.core/- 1 2) 3)

I'm pretty sure I'm representing my trees correctly because when I execute them I get the right answer. Does zipper expect a different layout?

+1  A: 

The tree isn't how you've diagrammed it. The root node has 3 children: +, (- 1 2), and 3. When you do down from the root node, it defaults to the left-most child, hence why you see +.

To get to the - you'd need to call:

user=> (-> zipped zip/down zip/right zip/down zip/node)
clojure.core/-
Alex Taggart
+2  A: 

The problem is that there are two different ideas of tree going on here. Your tree is a graph of how the values percolate through the evaluation, but LISP is thinking about lists of lists, and using prefix notation:

'(+ (- 1 2) 3) is also (list + (list - 1 2) 3), which is actually this tree:

+  .     3
   - 1 2

(-> zipped down node) gives you the first element, +, an atom. (-> zipped down down) thus gives you nil because the first element, +, is an atom. (-> zipped down right down node) gives you the minus sign you want because that's the first element of the second element of the expression.

John Lawrence Aspden
Thanks for that explanation, it cleared things up for me. I don't think I need to traverse the tree in the order in which it's executed, so I can probably still use Zipper.
Craig Glennie