clojure - 种植我的 Clojure 树

Question

我希望有人能提供帮助，所以我正在从 OOP 飞跃到函数式编程，这有点令人生畏!我正在尝试编写一个函数，它将返回子树中数字的总和，但我只想返回值更大的子树。如果这有意义？我已经编写了一个返回总树 maxsum 但想扩展的函数

例如:

         []
         |
    ---------
    |        |
    []      []    
   / \      /\
  1   []   3  []    <--biggest sub-tree
      /\      /\
     3  2    8  8

(defn is-tree [tr]
  (and (seq? tr) (not (empty? tr))))

(defn tree-total [tree]
  (cond
    (number? tree) tree

    (is-tree tree)
    (+ (tree-total (first tree))
      (tree-total (rest tree)))

    :else 0
    ))

就我而言，这让我了解了整个事情，但我无法实现它只对子树进行数学运算......有人能帮我吗？

我有一半的解决方案，但它并没有让我得到任何地方，这是......

(let [l-s-tree (myhelperfunc? (first tree))
      r-s-tree (myhelperfunc? (last tree))

      lt (tree-sum (first tree))
      rt (tree-sum (last tree))

      both (+ lt rt)]

但我无法将它实现到我当前的功能中，我完全不知道如何扩展它。谁能帮帮我？

Answer 1

树上的递归函数总是有点麻烦，尤其是当您尝试在 REPL 上测试它们时。这是我的尝试:

(defn max-subtree-sum [x]
  (if (coll? x) ;;Is this an internal node?
    (if (every? number? x) 
      ;;If every child is a number, we should sum them.
      (apply + x)
      ;;otherwise recur once for each child and take the max
      (apply max (map max-subtree-sum x)))
     x))

(max-subtree-sum [[1 [3 2]] [3 [8 8]]])
;; => 16
(max-subtree-sum '((1 (3 24)) (3 (8 8))));; Or with lists
;; => 27

我使用 coll? 来检查树性，因为在你的图表中它看起来像你的内部节点是向量，但事实证明它们不是 seq?我只是假设任何不是集合的东西都是数字——如果你有一个更混合的数据树，你应该能够通过用 替换外部 if 来处理它cond 和最后的 :else 0 子句，就像您尝试的那样。

这里的主要添加是在决定如何处理它们之前查看内部节点的子节点。如果它们都是数字，那么我们就是在求和。如果不是，那么我们就是一个完全内部的节点，需要取而代之的是 max。您可以使用 apply(基本上，(apply f [x y z]) 是 (f x y z) - 它将集合作为单独的参数插入到函数中)，一旦我们使用 map 递归地获取子树子树的 max-subtree-sum。