你會如何調用優化這個構建樹的Clojure函數？

Question

我有一些地圖

(def m1 [{:a 1, :b 2, :c 0} 
     {:a 1, :b 3, :c 0} 
     {:a 1, :b 0, :c 2} 
     {:a 1, :b 3, :c 1} 
     {:a 1, :b 0, :c 3}]) 

，我可以遞歸組與該功能

(defn group [ks coll] 
    (if (empty? ks) coll 
     (let [gs (group-by #(select-keys % [(first ks)]) coll)] 
     (map (fn [[k v]] {k (group (rest ks) v)}) (dissoc gs {}))))) 

，以產生預期的結果：

(group [:a :b :c] m1) 

=>

({{:a 1} ({{:b 2} ({{:c 0} [{:a 1, :b 2, :c 0}]})} 
      {{:b 3} ({{:c 0} [{:a 1, :b 3, :c 0}]} 
        {{:c 1} [{:a 1, :b 3, :c 1}]})} 
      {{:b 0} ({{:c 2} [{:a 1, :b 0, :c 2}]} 
        {{:c 3} [{:a 1, :b 0, :c 3}]})})}) 

你怎麼能改寫這樣，在最後一個位置具有map的功能，因爲它需要遵循多條路徑，是尾調用使用recur優化的？

Answer 1

你原來的算法要求節點的當前兄弟姐妹經常性時將被保留作爲背景，這樣我們就可以返回到反覆的底部後處理這些兄弟姐妹。稍作修改，我們就可以一次構建一個節點的完整路徑，深度優先，忽略節點之間的關係。這允許更簡單的尾部呼叫遞歸。

(defn group [ks coll] 
    (group-recur ks coll ks [] {})) 

(defn- group-recur [ks coll recur-keys path acc] 
    (if (empty? coll) 
    acc 
    (if (empty? recur-keys) 
     (recur ks (rest coll) ks [] (assoc-in acc path (first coll))) 
     (let [node (first coll) 
      rk (first recur-keys) 
      k (select-keys node [rk]) 
      p (conj path k)] 
     (recur ks coll (rest recur-keys) p acc))))) 

這裏是online Repl來嘗試一下。

Answer 2

哦，原來是極其複雜的。我成功地實現上述使用loop/recur有點像，但我已經向大家介紹了一堆的輔助功能，以保持它有點可讀：

(defn group-recur [ks coll] 
    (let [split-map (fn [m] 
        (->> m 
         (into []) 
         (map (partial apply hash-map)))) 
     dissoc-non-map (fn [m k] 
         (let [l (drop-last k)] 
          (if-not (map? (get-in m k)) 
          (if (empty? l) 
           (dissoc m (last k)) 
           (update-in m l dissoc (last k))) 
          m))) 
     updater (fn [r k v] 
        (let [s (split-map k)] 
        (-> r 
         (dissoc-non-map (drop-last s)) 
         (assoc-in s v))))] 
    (loop [k ks 
     h [] 
     r {}] 
    (if (not-empty k) 
     (let [all (conj h (first k)) 
      grouped (dissoc (group-by #(select-keys % all) coll) {})] 
     (->> grouped 
      (reduce-kv updater r) 
      (recur (rest k) 
        all))) 
     r)))) 

它返回地圖的樹，而不是你上面使用的集合（其我認爲更合乎邏輯）。基本前提是，您沿着結果地圖傳遞並隨時更新它。這就是爲什麼dissoc-non-map在那裏，如果在更高層次上已經存在另一個非地圖值，那麼在地圖中很可能不會出現assoc-in。

循環需要3個參數：鍵的列表中仍然要處理，我們已經當前處理的鍵/值對（如果你願意，也就是現在的「樹中的位置」），並將得到的地圖樹。一個最終的結果，和一個與中間值：

一種替代（一個可能簡單）實現可以沿兩個映射通過。這應該消除對dissoc-non-map的需求。