如何实现分层步骤序列的嵌套？（Clojure技术场景）

需求回顾 #

给定如下步骤列表：

[{:id 1 :layer :foo}
 {:id 2 :layer :foo/bar}
 {:id 3 :layer :foo}
 {:id 4 :layer :bar/baz}
 {:id 5 :layer :foo/bar}
 {:id 6 :layer :foo/baz}
 {:id 7 :layer :foo/baz}
 {:id 8 :layer :foo/baz}
 {:id 9 :layer :foo/baz}
 {:id 10 :layer :foo}]

需要将其转换为按:layer路径嵌套的序列，最终输出：

[{:layer :foo :steps [1 {:layer :foo/bar :steps [2]} 3]}
 {:layer :bar :steps [{:layer :bar/baz :steps [4]}]}
 {:layer :foo :steps [{:layer :foo/bar :steps [5]}
                      {:layer :foo/baz :steps [6 7 8 9]}
                      10]}]

惯用风格的实现方案 #

我们可以用纯函数式的reduce结合栈状态管理来实现，这比冗长的loop更符合Clojure的惯用风格，逻辑清晰且易维护。

核心实现代码 #

(defn split-layer [layer]
  ;; 将:foo/bar这类层级路径拆分为[:foo :bar]的序列
  (map keyword (clojure.string/split (name layer) #"/")))

(defn make-node [path]
  ;; 根据路径片段生成嵌套节点
  {:layer (keyword (clojure.string/join "/" (map name path)))
   :steps []})

(defn nest-steps [steps]
  (letfn [(common-depth [path1 path2]
            ;; 计算两个路径的共同前缀长度（层级深度）
            (count (take-while (fn [[a b]] (= a b)) (map vector path1 path2))))]
    (->> (reduce
          (fn [[result stack] {:keys [id layer]}]
            (let [current-path (split-layer layer)
                  ;; 获取当前栈中所有层级的路径
                  stack-paths (map :path stack)
                  ;; 计算当前目标路径与栈顶路径的共同深度
                  current-common (if (empty? stack-paths)
                                   0
                                   (common-depth (last stack-paths) current-path))
                  ;; 弹出栈中超过共同深度的节点，并入结果列表
                  [popped new-stack] (split-at (- (count stack) current-common) stack)
                  new-result (into result (map :node) popped)
                  ;; 构建从共同深度到目标路径的所有中间层级节点
                  [temp-stack _]
                  (reduce
                   (fn [[s parent-node] depth]
                     (let [sub-path (take depth current-path)
                           sub-node (make-node sub-path)]
                       (if parent-node
                         ;; 更新父节点的steps，替换栈中的父节点
                         (let [updated-parent (update parent-node :steps conj sub-node)]
                           [(conj (pop s) (assoc (last s) :node updated-parent) {:path sub-path :node sub-node})
                            sub-node])
                         ;; 无父节点，直接将新节点加入栈
                         [(conj s {:path sub-path :node sub-node}) sub-node])))
                   [new-stack (when (seq new-stack) (:node (last new-stack)))]
                   (range (inc current-common) (inc (count current-path))))
                  ;; 将当前步骤ID加入最内层节点的steps
                  inner-node (:node (last temp-stack))
                  updated-inner (update inner-node :steps conj id)
                  updated-stack (conj (pop temp-stack) (assoc (last temp-stack) :node updated-inner))]
              [new-result updated-stack]))
          [[] []]
          steps)
         ;; 将栈中剩余的节点并入最终结果
         (apply into)
         vec)))

实现逻辑说明 #

1. 路径拆分：split-layer函数将命名空间风格的层级路径拆分为片段序列，方便层级对比。
2. 节点生成：make-node根据路径片段生成标准的嵌套节点结构。
3. Reduce循环处理：
   • 维护两个状态：最终结果列表result和当前层级栈stack（栈中每个元素包含路径和对应的节点）。
   • 对于每个步骤，先回溯到目标路径与当前栈的共同父层级，弹出多余的节点到结果中。
   • 构建缺失的中间层级节点，将其加入父节点的steps并更新栈。
   • 将当前步骤的ID添加到最内层节点的steps中。
4. 收尾处理：将栈中剩余的未闭合节点全部加入结果列表。

替代方案说明 #

Zipper确实可以处理这类嵌套结构的修改，但学习成本较高，对于这种线性遍历+层级切换的场景，reduce结合栈的方式更直观，代码也更易读和维护，完全符合Clojure的函数式编程惯用风格。

内容的提问来源于stack exchange，提问作者Lēctia Landau