Inserisci somma di tutti i rami parentali in ciascun ramo di una struttura ad albero nidificato

Question

In una struttura ad albero, come può un valore/chiave essere unito a ogni ramo in cui il valore è la somma del valore del ramo e tutti i valori del ramo padre?

Ad esempio, partendo con struttura ad albero segue:

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

come potrebbe essere ricreato come:

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

ho cercato con walk. Penso che questo potrebbe essere l'approccio corretto. Ma finora non ci sono riuscito.

Answer 1

Penso che questa funzione ricorsiva faccia il trucco.

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

quando valutato nel modo seguente:

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

[(sums (first root) 0)] 

risultati in:

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

O Ecco una versione più amichevole della stessa funzione sums per il formato di albero.

(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 

Answer 2

Per motivi di confronto, ecco una versione che utilizza clojure.walk. Penso che questa sia una situazione in cui una funzione ricorsiva personalizzata sarà più pulita rispetto all'utilizzo di walk. Una funzione personalizzata consente di passare i risultati intermedi (nella forma della somma dei genitori) dal genitore al figlio come parametro di funzione, mentre la funzione che si passa a camminare non ha parametri aggiuntivi oltre alla forma percorsa, quindi devi registrare risultati intermedi nei dati stessi mentre attraversi l'albero.

(require '[clojure.walk :as walk]) 

(defn sums 
    [x] 
    (walk/prewalk (fn [m] 
        (if (map? m) 
        (let [v (or (:v m) 0) 
          s (+ v (or (:sum m) 0)) 
          m (assoc m :sum s)] 
         (if (seq (:_ m)) 
         (update-in m [:_] 
            (partial map (fn [c] (assoc c :sum s)))) 
         m)) 
        m)) 
       x)) 

Answer 3

Una soluzione cerniera potrebbe scrivere

(require '[clojure.zip :as z]) 

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

(def zipper (partial z/zipper :_ :_ (fn [n ch] (assoc n :_ (vec ch))))) 

(loop [node (zipper (first root))] 
    (if (z/end? node) 
    (z/root node) 
    (recur 
     (z/next 
     (z/edit node 
       #(assoc % :sum ((fnil + 0) %2 (:v %))) 
       (some-> node z/up z/node :sum)))))) 

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

che si potrebbe avvolgere di nuovo in un vettore se lo si desidera. Nota: la "radice" come definita non corrisponde al resto della struttura ad albero quando è avvolta in un vettore, motivo per cui abbiamo una "(prima radice)".