Print a tree lazily in Newick format

Question

I want to print a binary tree in Newick , showing each distance of the node to its parent. At the moment, I had no problem with the following code that uses regular recursion, but too deep a tree could lead to a stack overflow.

(defn tree->newick [tree] (let [{:keys [id children to-parent]} tree dist (double to-parent)] ; to-parent may be a rational (if children (str "(" (tree->newick (first children)) "," (tree->newick (second children)) "):" dist) (str (name id) ":" dist)))) (def example {:id nil :to-parent 0.0 :children [{:id nil :to-parent 0.5 :children [{:id "A" :to-parent 0.3 :children nil} {:id "B" :to-parent 0.2 :children nil}]} {:id "C" :to-parent 0.8 :children nil}]}) (tree->newick example) ;=> "((A:0.3,B:0.2):0.5,C:0.8):0.0" (def linear-tree (->> {:id "bottom" :to-parent 0.1 :children nil} (iterate #(hash-map :id nil :to-parent 0.1 :children [% {:id "side" :to-parent 0.1 :children nil}])) (take 10000) last)) (tree->newick linear-tree) ;=> StackOverflowError 

The problem I found with current utilities like tree-seq and clojure.walk is that I need to clojure.walk over the internal node several times to insert a comma and close the bracket. I used clojure.zip , but I was not able to write a lazy / tail recursive implementation, since I would need to store for each internal node how many times they have been visited.

Answer 1

Here is the version that works on your linear-tree example. This is a direct transformation of your implementation with two changes: it uses a continuation style and a trampoline.

 (defn tree->newick ([tree] (trampoline tree->newick tree identity)) ([tree cont] (let [{:keys [id children to-parent]} tree dist (double to-parent)] ; to-parent may be a rational (if children (fn [] (tree->newick (first children) (fn [s1] (fn [] (tree->newick (second children) (fn [s2] (cont (str "(" s1 "," s2 "):" dist)))))))) (cont (str (name id) ":" dist)))))) 

Edit : Added template matching, which allows you to simply call a function.

Change 2 . I noticed that I was mistaken. The problem is that I really accepted the fact that Clojure does not optimize tail calls only partially into account.

The main idea of ​​my solution is to convert to a continuation transfer style, so recursive calls can be moved to the tail position (i.e., instead of returning their result, recursive calls pass it on as an argument).

Then I manually optimized recursive calls, forcing them to use a trampoline. I forgot to consider that continuation calls, which are not recursive calls, but also in the tail position, also need to be optimized, since tail calls can be a very long chain of closures, so when the function finally evaluates them, it becomes a long chain of calls.

This problem did not materialize with the linear-tree test data, because the continuation for the first child returns to the trampoline to handle the recursive call for the second child. But if the linear-tree changed so that it uses the second child of each node to build a linear tree instead of the first child, this again causes a stack overflow.

Thus, appeals of follow-ups should also return to the springboard. (Actually, a call in the base case does not happen without children, because it will happen no more than once before returning to the springboard, and then this will be true for the second recursive call.) So, here is an implementation that takes this into account and should use only constant stack space on all inputs:

 (defn tree->newick ([tree] (trampoline tree->newick tree identity)) ([tree cont] (let [{:keys [id children to-parent]} tree dist (double to-parent)] ; to-parent may be a rational (if children (fn [] (tree->newick (first children) (fn [s1] (tree->newick (second children) (fn [s2] #(cont (str "(" s1 "," s2 "):" dist))))))) (cont (str (name id) ":" dist))))))