从Clojure中的向量构建树

Question

我正在研究我的第一个Clojure计划.我有一些问题想出如何基于如下所示的输入构建树:

["A B" "A C" "C D" "D E" "A F" "F G"]

输出应该是这样的:

'(A (B) (C (D (E)) (F (G)))

我不知道如何开始这样做.例如,当涉及到命令式编程时,我会使用嵌套循环来查找这种关系是否已经存在,当它不存在时,我会找到父元素并将子元素附加到它.但据我所知,函数式编程将使用另一种方法,我将递归地遍历向量中的所有元素,而不是更改现有的树,我构建了一个新的.

我不确定这是否有效,但我有一个看起来像这样的功能:

(defn build-tree
  [func tree parent child]
  (map (fn [i] (if (seq? i)
                 build-tree
                 (func i parent child))))) 

我确定这个问题来自于我对Clojure和函数式编程的不熟悉,并且希望有人可以解释使用递归和构建这个树的最佳方法.

Answer 1

您可能会收到比我下面更短的答案.我决定教你钓鱼 - 而不是展示一个简短的课程,我将带你通过系统的方式来解决这类问题.您将不得不填写一些空白,包括将您的数据转换为更可口的形式.这些是小点,只会分散注意力.

您需要做的第一件事是将输出分解为构造步骤.这些步骤应与输出所代表的抽象类型相匹配.在您的情况下,输出的具体类型是一个列表,但它实际上代表一棵树.这些是不同的抽象类型 - 列表有头部和尾部,就是它,但树有节点,可能有孩子.您需要根据构建不同类型节点的抽象构造函数进行思考,而不是考虑您选择代表抽象类型的偶然特定结构 - 在您的案例中是一个列表.

所以想象一下,你有两个看起来像的构造函数

(defn ->branch
  [id kids]
  ...)

(defn ->leaf
  [id]
  ...)

当然,假设每一kid棵树都是树 - 也就是树枝或树叶.换句话说,每一个都kid应该是->branch或者的结果->leaf.

因此,构建任何树的唯一方法是使用嵌套的构造函数调用链.这就是我所说的"将输出分解为施工步骤".在您的情况下,它意味着以下链:

(->branch :A [(->leaf :B) (->branch :C [(->branch :D (->leaf :E))]) (->branch :F [(->leaf :G)])])

(我将使用关键字而不是节点ID的符号,否则我们将陷入绑定/引用细节的困境.)

在这里停留一秒钟,感受功能和命令式风格之间的区别.您自己概述了命令式样式 - 您可以通过找到正确的位置并在其中添加新节点来更新树.在功能样式中,您可以考虑创建值,而不是更新其他值.(当然,在技术上没有任何东西阻止你在命令式语言中做同样的事情 - 比如使用嵌套调用构造函数,或者以这种方式使用静态工厂,这不是自然而然的事情.)

为了让您的具体树表示为一个列表,你只需要填写的实施->branch和->leaf上面,这是非常简单的.(留给你练习.)

现在回到构建树.编写构建树的函数的任务实际上是从输入数据创建一系列构造函数调用.所以你需要了解两件事:

• 何时调用哪个构造函数(此处,何时调用->branch以及何时调用->leaf)
• 如何获取构造函数的参数(idfor和kidsfor ->branch)

首先,我们如何知道要开始的节点？这取决于问题所在,但我们假设它是作为参数给出的.所以我们假设我们正在构建以下函数:

(defn ->tree
  [adj-list node]
  ...)

这adj-list是你的输入 - 即使你试图将它伪装成一个字符串列表,它也是一个邻接列表,我们将以这种方式对待它(如评论中建议的@SamEstep).留下作为练习让你转换您在邻接列表中的输入形式.

所以应该清楚我们id在构造函数中使用的是什么- node.但是它->branch还是->leaf？那么,答案取决于我们是否有直接后代node的adj-list,所以显然我们需要一个功能

(defn descendants
  [adj-list node]
  ...)

它返回一个直接后代的id列表(可能是空的)node.(左边作为练习.)所以我们可以决定是否打电话->branch或->leaf取决于该列表是否为空,如

(if-let [kid-ids (descendants node)]
   (->branch node ...)
   (->leaf node))

好吧,那么我们就需要提供这些...来->branch.是kid-ids吗？不,它们必须是树木,而不是ids,树枝或树叶本身.换句话说,我们需要先调用->tree它们.看到？我们达到了递归点,它自然而然地产生(或者我希望如此).在Clojure中,在序列的每个元素上调用一个函数map,它返回一个结果序列,这正是我们所需要的:

(if-let [kid-ids (descendants adj-list node)]
   (->branch node (map ->tree kid-ids)
   (->leaf node))

除了->tree需要一个额外的参数,adj-list.我们可以使用匿名函数,或者我们可以使用partial.我们将使用partial带有let绑定的绑定,这是最干净的方法:

(let [->tree' (partial ->tree adj-list)]
   (if-let [kid-ids (descendants adj-list node)]
      (->branch node (map ->tree' kid-ids))
      (->leaf node)))

就是这个.我们把它放在一起:

(defn ->tree
  [adj-list node]
  (let [->tree' (partial ->tree adj-list)]
     (if-let [kid-ids (descendants adj-list node)]
       (->branch node (map ->tree' kid-ids))
       (->leaf node))))

结果:

(def adj-list [[:A :B] [:A :C] [:C :D] [:D :E] [:A :F] [:F :G]])

(->tree adj-list :A)
;; => (:A (:B) (:C (:D (:E))) (:F (:G)))

我们总结一下:

• 用抽象的术语看你的数据.创建构造函数,并使用它们来构建输出.
• 构建输出意味着创建一系列构造函数调用.
• 这意味着您需要将输入的形状映射到输出构造函数及其参数.
• 在许多情况下,递归将在此步骤中自然出现.

完成后,你可以优化和短路你的内容(就像你仔细观察,你可以取消->leaf.)但不要过早地做.