你将如何尾调用优化这个构建树的 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

好吧，事实证明它非常复杂。我设法使用 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))))

它 returns 一棵地图树，而不是您上面使用的集合（我认为这更合乎逻辑）。基本前提是您传递结果地图并在传递过程中更新它。这就是 dissoc-non-map 在那里的原因，显然如果在更高级别上已经存在另一个非地图值，则您不能在地图中 assoc-in。

循环需要 3 个参数：仍待处理的键列表、我们当前处理的 key/value 对（即当前的 "position in the tree"，如果你愿意的话）和生成的映射树.

另一种（可能更简单的）实现可以传递两个映射：一个是最终结果，另一个是中间值。那应该消除对 dissoc-non-map.

的需要

Answer 2

你原来的算法要求在递归的时候把当前的兄弟结点作为context保存下来，这样我们可以return在递归到底层之后再去处理那些兄弟结点。通过稍微修改，我们可以一次构建到一个节点的完整路径，深度优先，忽略节点之间的关系。这允许更简单的尾调用递归。

(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 来试试看。

你将如何尾调用优化这个构建树的 Clojure 函数？

How would you tail call optimize this Clojure function that builds a tree?

tail-recursion

clojure