Re: replace-subtree for zippers?
Meikel Brandmeyer m...@kotka.de writes: Hi, On Aug 21, 12:05 pm, Jan Rychter j...@rychter.com wrote: It isn't what I want. But that's because I misspecified what I actually wanted. I didn't think about the problem enough. I need something more akin to a splice function: (splice tree1 index tree2) (splice '(1 2 (3 4 5) 6) 4 '(7 8 (9 10))) should produce = '(1 2 (3 7 8 (9 10) 6)) (defn zip-splice [loc node new-node] (loop [loc loc] (cond (zip/end? loc) (throw (Exception. Node not found)) (= (zip/node loc) node) (let [childs (zip/children new-node) loc(reduce #(zip/insert-left %1 %2) loc childs)] (zip/remove loc)) :else (recur (zip/next loc) user= (def z (zip/vector-zip [1 2 [3 4 5] 6])) #'user/z user= (def s (zip/vector-zip [7 8 [9 10]])) #'user/s user= (zip/root (zip-splice z 4 s)) [1 2 [3 7 8 [9 10] 5] 6] Be aware of the '=' there. This you might want to replace with some smarter function to check for the identity of a node. I stumpled over that in this thread: http://groups.google.com/group/clojure/browse_thread/thread/bfd6539ec367a95b I'm not really a tree expert. So if you have solved this problem, please let me know. I'm still interested in this. Thanks -- this is good stuff. I appreciate the help. I meant the index as a numeric index into the tree (depth-first traversal), unrelated to the actual tree contents -- I used natural numbers in the tree only as an example. My real trees contain mostly symbols. So your function isn't applicable to my stuff. In the meantime, I came up with this (nothing like a piece of paper and some thinking to work things out): (defn zip-splice [zipped-tree index loc2] (let [splice-site (goto-node zipped-tree index)] (zip/root (zip/replace (zip/up splice-site) (concat (zip/lefts splice-site) (list (zip/node loc2)) (zip/rights loc2)) where goto-node is defined as: (defn goto-node [zipped-code n] (loop [counter 0 loc (zip/next zipped-code)] (if (or (= counter n) (zip/end? loc)) loc (recur (inc counter) (zip/next loc) This seems to do exactly what I wanted. --J. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@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+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: replace-subtree for zippers?
Stefan van der Meer stefanvanderm...@gmail.com writes: On Aug 21, 12:05 pm, Jan Rychter j...@rychter.com wrote: think crossover in genetic programming (this is actually what I need this for). I've written a genetic programming framework in Clojure, it might be of interest if you're looking for some inspiration: http://bitbucket.org/svdm/clojuregp/src/ I didn't know about this -- thanks, I will definitely check it out. Though I experimented with using zippers initially, I ended up not using them for the fundamental tree operations like the one discussed here. I found zippers to be quite a bit slower than more low level approaches for traversing trees, which becomes significant in typical GP experiments where things like subtree replacement are used a large number of times. Interesting. I don't see why zippers would be much slower than other approaches, unless manipulating metadata in Clojure is excessively slow. In my case, I don't much care, because my program spends most of the time in fitness evaluations. Actual code manipulation takes only a small percentage of the time and isn't worth worrying about (so far). [...] So that's one way of doing it. Not the prettiest, but it does what I need it to. I'm not sure it does exactly what you want though, because: user (tree-replace 3 '(7 8 (9 10)) '(1 2 (3 4 5) 6)) (1 2 (3 (7 8 (9 10)) 5) 6) Compared to: should produce = '(1 2 (3 7 8 (9 10) 6)) I'm kind of wondering why you want the replacement subtree (tree2 if you will) to be spliced flat into the original tree like that. It seems to me that such an operation would not actually do a subtree replacement in the typical genetic programming sense. Flat splicing-in makes sense, because my GP is a stack-based one (a concatenative language, inspired by PushGP and Forth). Programs are really flat sequences of instructions and constants. Trees arise only because I want the language to have loops and function/code generation facilities. A subtree is a piece of code that gets pushed onto the code stack, to be executed later. For simple tasks, flat sequences of instructions would be enough and indeed this is the primary mechanism. Here are three examples that hopefully illustrate the concept: (1 2 int+) = 3 (2 (1 int+) exec) = 3 (2 (1 int+) 3 dotimes) = 5 As you can see, I really do want the crossover operator to splice code flat into the original tree. Adding a subtree has an entirely different meaning. You might want to look at stack-based GP. I think it is much more flexible than code trees. --J. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@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+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: replace-subtree for zippers?
I've dabbled in genetic programming as well. My approach to crossover is simply to return a seq of indices to the node. Then you can just use nth repeatedly, or if your trees are nested vecs, you can use assoc-in directly. Then I just eval'd a fn and map-reduce'd it across my test data. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@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+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: replace-subtree for zippers?
Meikel Brandmeyer m...@kotka.de writes: A transcript: ; Create trees... user= (def t1 [1 [[2 3] 4]]) #'user/t1 user= (def t2 [[[:a :b] :c] :d]) #'user/t2 ; Create zippers and navigate to subtrees... user= (def zt1 (- (zip/vector-zip t1) zip/down zip/right)) #'user/zt1 user= (zip/node zt1) [[2 3] 4] user= (def zt2 (- (zip/vector-zip t2) zip/down)) #'user/zt2 user= (zip/node zt2) [[:a :b] :c] ; Replace the subtree from first zipper with subtree from second zipper... user= (def zt1 (zip/replace zt1 (zip/node zt2))) #'user/zt1 user= (zip/root zt1) [1 [[:a :b] :c]] Isn't that what you want? It isn't what I want. But that's because I misspecified what I actually wanted. I didn't think about the problem enough. I need something more akin to a splice function: (splice tree1 index tree2) (splice '(1 2 (3 4 5) 6) 4 '(7 8 (9 10))) should produce = '(1 2 (3 7 8 (9 10) 6)) think crossover in genetic programming (this is actually what I need this for). --J. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@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+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: replace-subtree for zippers?
On Aug 21, 12:05 pm, Jan Rychter j...@rychter.com wrote: think crossover in genetic programming (this is actually what I need this for). --J. Hi, I've written a genetic programming framework in Clojure, it might be of interest if you're looking for some inspiration: http://bitbucket.org/svdm/clojuregp/src/ Though I experimented with using zippers initially, I ended up not using them for the fundamental tree operations like the one discussed here. I found zippers to be quite a bit slower than more low level approaches for traversing trees, which becomes significant in typical GP experiments where things like subtree replacement are used a large number of times. After some experimentation I settled on an approach using an atom to keep track of the current node's index in the tree, while walking it depth-first, rebuilding it as we go. If the index matches the one we want to replace, we cons on the replacement node instead of the old one. This turns out to be pretty fast, but it's a bit of a monstrosity, what with the mutable state, etc. I've been meaning to replace it with something nicer, but haven't found a good alternative yet. Here it is: (defn tree-replace [idx new-node tree] (let [i (atom -1) r-fn (fn do-replace [node] (swap! i inc) (cond (= @i idx) new-node ( @i idx) node (coll? node) (cons (first node) (doall (map do-replace (next node :else node))] (r-fn tree))) Also available here if it gets mangled: http://bitbucket.org/svdm/clojuregp/src/tip/src/cljgp/breeding.clj#cl-111 The index of each node is equal to its index in a tree-seq created as follows: (tree-seq coll? next tree) In action: user (def tree1 '(- 100 99)) #'user/tree1 user (def tree2 '(+ (* 1 2) (- 3 4))) #'user/tree2 user (tree-seq coll? next tree2) ((+ (* 1 2) (- 3 4)) (* 1 2) 1 2 (- 3 4) 3 4) user (tree-replace 1 tree1 tree2) (+ (- 100 99) (- 3 4)) user (tree-replace 2 tree1 tree2) (+ (* (- 100 99) 2) (- 3 4)) user (tree-replace 0 tree1 tree2) (- 100 99) So that's one way of doing it. Not the prettiest, but it does what I need it to. I'm not sure it does exactly what you want though, because: user (tree-replace 3 '(7 8 (9 10)) '(1 2 (3 4 5) 6)) (1 2 (3 (7 8 (9 10)) 5) 6) Compared to: should produce = '(1 2 (3 7 8 (9 10) 6)) I'm kind of wondering why you want the replacement subtree (tree2 if you will) to be spliced flat into the original tree like that. It seems to me that such an operation would not actually do a subtree replacement in the typical genetic programming sense. I've tried to illustrate what I mean in a little diagram: http://i30.tinypic.com/hsizkh.png Regards, Stefan PS. I hope this ends up in the right place, I'm new to mailing list posting. Apologies in advance if I accidentally break something. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@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+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
Re: replace-subtree for zippers?
Hi, A transcript: ; Create trees... user= (def t1 [1 [[2 3] 4]]) #'user/t1 user= (def t2 [[[:a :b] :c] :d]) #'user/t2 ; Create zippers and navigate to subtrees... user= (def zt1 (- (zip/vector-zip t1) zip/down zip/right)) #'user/zt1 user= (zip/node zt1) [[2 3] 4] user= (def zt2 (- (zip/vector-zip t2) zip/down)) #'user/zt2 user= (zip/node zt2) [[:a :b] :c] ; Replace the subtree from first zipper with subtree from second zipper... user= (def zt1 (zip/replace zt1 (zip/node zt2))) #'user/zt1 user= (zip/root zt1) [1 [[:a :b] :c]] Isn't that what you want? Sincerely Meikel --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@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+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~--~~~~--~~--~--~---
