clojure - 如何在 Clojure 中使用尾递归遍历 AST

Question

我有一个 ANTLR3 AST，我需要使用后序深度优先遍历来遍历它，我大致实现了以下 Clojure:

(defn walk-tree [^CommonTree node]
  (if (zero? (.getChildCount node))
    (read-string (.getText node))
    (execute-node
      (map-action node)
      (map walk-tree (.getChildren node)))))))

我想使用 loop...recur 将其转换为尾递归，但我一直无法弄清楚如何有效地使用显式堆栈来执行此操作，因为我需要一个后序遍历。

Answer 1

您可以使用 tree-seq 生成深度优先遍历的惰性序列，而不是生成遍历树并访问每个节点的尾递归解决方案。函数，然后从遍历中的每个对象中获取文本。惰性序列永远不会炸毁堆栈，因为它们存储了在堆中生成序列中的下一项所需的所有状态。它们经常被用来代替这样的递归解决方案，其中 loop和 recur更难。

我不知道你的树是什么样子，尽管典型的答案看起来像这样。您需要使用“有 child ”“ child 列表”功能

(map #(.getText %) ;; Has Children?      List of Children    Input Tree
     (tree-seq #(> (.getChildCount #) 0) #(.getChildren %) my-antlr-ast))

如果 tree-seq 不适合您的需要，还有其他方法可以从树中生成惰性序列。接下来看 zipper 库。