java - 可变树到持久树

Question

学习 Clojure(和函数式编程)我偶然发现了将表示为嵌套 java.util.ArrayList 的可变 n 叉树转换为持久树的问题。

使用非函数式编程，您通常会创建从根到叶的树。使用持久数据结构这似乎是不可能的。

谁能告诉我如何在给定可变 n 叉树的情况下构造一棵不可变树？

Answer 1

与大多数函数一样，答案是递归。实际上，与通过改变 java 中的一堆列表列表相比，在功能上做起来要容易得多。您只需定义一个将单个 ArrayList 转换为 clojure 列表的函数，然后让该函数在任何子列表上递归调用自身。这是最简单的答案；如果你想支持 map 而不是列表或其他任何东西，你可以添加装饰。

(import '(java.util List ArrayList))
(defn lists->tree [x]
  (if (instance? List x)
    (map lists->tree x)
    x))

(lists->tree (ArrayList. [(ArrayList. [1 2 3])
                          (ArrayList. [(ArrayList. [4 5])
                                       (ArrayList. [6])])]))
((1 2 3) ((4 5) (6)))