clojure - 在嵌套树结构的每个分支中插入所有父分支的总和

Question

在树结构中，如何将键/值与每个分支合并，其中值是分支值和所有父分支值的总和？

例如，从以下树结构开始:

[{  :v 1
    :_ [{ :v 2 }
        { :v 3
          :_ [{ :v 5 }]}
        { :v 4 }]}]

如何将其重新创建为:

[{  :v 1
    :sum 1
    :_ [{ :v 2
          :sum 3 }
        { :v 3
          :sum 4
          :_ [{ :v 5
                :sum 9 }]}
        { :v 4
          :sum 5 }]}]

我一直在尝试 walk .我认为这可能是正确的方法。但是，到目前为止我还没有做到。

Answer 1

我认为这个递归函数可以解决问题。

(defn sums [{v :v children :_} sum]
  {:v v
   :sum (+ sum v)
   :_ (mapv #(sums % (+ sum v)) children)})

按以下方式评估时:

(def root
   [{:v 1
      :_ [{:v 2}
          {:v 3
           :_ [{:v 5}]}
          {:v 4}]}])    

[(sums (first root) 0)]

结果是:

[{:v 1,
  :sum 1,
  :_ [{:v 2,
       :sum 3,
       :_ []}
      {:v 3,
       :sum 4,
       :_ [{:v 5,
            :sum 9,
            :_ []}]}
      {:v 4,
       :sum 5,
       :_ []}]}]

或者这里有一个更友好的版本 sums树格式的函数。

(defn sums [root]
  (letfn [(f [{v :v children :_} sum]
            {:v v
             :sum (+ sum v)
             :_ (mapv #(f % (+ sum v)) children)})]
    [(f (first root) 0)]))

(sums root)
;= same result as before