以紐尼克格式懶洋洋地打印一棵樹

Question

我希望在Newick format中打印一棵二叉樹，顯示每個節點與其父節點的距離。目前我沒有遇到下面的代碼使用正則遞歸的問題，但是太深的樹可能會產生堆棧溢出。

(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 

我已經與當前的工具，如tree-seq和clojure.walk發現的問題，是我要拜訪的內部節點不止一次，以夾着逗號和關閉支架。我用clojure.zip，但沒有設法寫一個懶/尾遞歸實現，因爲我需要爲每個內部節點存儲它們已經訪問了多少次。

Answer 1

以下是適用於您的linear-tree示例的版本。這是一個直接轉換你的實現兩個變化：它使用延續傳球風格和蹦牀。

(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)))))) 

編輯：添加模式匹配，允許調用一個簡單的方法的功能。

編輯2：我注意到我犯了錯誤。問題是，我確實認爲Clojure並沒有只考慮部分尾部呼叫。

我的解決方案的核心思想是轉換爲延續傳遞樣式，以便遞歸調用可以移動到尾部位置（即不是返回它們的結果，遞歸調用將它作爲參數傳遞給繼續）。

然後，我通過使用蹦牀手動優化了遞歸調用。我忘記考慮的是繼續的調用 - 不是遞歸調用，而是尾部調用 - 也需要進行優化，因爲尾部調用可能是一個非常長的閉包鏈，所以當函數最終評估它們，它變成一個長長的呼叫鏈。

由於第一個孩子的繼續返回到蹦牀以處理第二個孩子的遞歸調用，所以該問題沒有與測試數據linear-tree實現。但是，如果更改了linear-tree，以便它使用每個節點的第二個子節點構建線性樹而不是第一個子節點，則會再次導致堆棧溢出。

因此，繼續的調用也需要返回到蹦牀。 （實際上，沒有兒童基本情況下的調用不會，因爲它在返回蹦牀之前最多隻會發生一次，而對於第二次遞歸調用，情況也是如此）。所以這裏有一個實現，它考慮到了這一點並且應該在所有輸入上僅使用恆定堆棧空間：

(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))))))