clojure - Clojure平面序列成树

Question

我有以下向量， [-1 1 2 -1 3 0 -1 2 -1 4 0 3 0 0]

代表树[[1 2 [3] [2 [4] 3]]]

其中 -1 开始一个新分支，0 结束它。如何将原始向量转换为可用的树状 clojure 结构（嵌套向量、嵌套映射）？我认为clojure.zip/zipper可能会这样做，但我不确定如何构建这些函数 args。

Answer 1

拉链是一个很好的工具： 

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

(def in [-1 1 2 -1 3 0 -1 2 -1 4 0 3 0 0])
(def out [[1 2 [3] [2 [4] 3]]])

(defn deepen [steps]
  (->> steps
       (reduce (fn [loc step]
                 (case step
                   -1 (-> loc
                          (zip/append-child [])
                          (zip/down)
                          (zip/rightmost))
                   0 (zip/up loc)
                   (zip/append-child loc step)))
         (zip/vector-zip []))
       (zip/root)))

(assert (= (deepen in) out))

Answer 2

不知何故，这感觉像是作弊：

[(read-string
  (clojure.string/join " "
                       (replace {-1 "[" 0 "]"}
                                [-1 1 2 -1 3 0 -1 2 -1 4 0 3 0 0])))]

Answer 3

这对于一些递归来说并不太难：

(defn numbers->tree [xs]
  (letfn [(step [xs]
            (loop [ret [], remainder xs]
              (if (empty? remainder)
                [ret remainder]
                (let [x (first remainder)]
                  (case x
                    0 [ret (next remainder)]
                    -1 (let [[ret' remainder'] (step (next remainder))]
                         (recur (conj ret ret'), remainder'))
                    (recur (conj ret x) (next remainder)))))))]
    (first (step xs))))

这个想法是有一个函数 ( step) 找到一个子树，并返回该树以及剩下哪些数字需要处理。它对大多数输入进行迭代（通过loop），并在遇到 时启动自身的递归实例-1。唯一棘手的部分是确保使用remainder从这些递归调用返回的，而不是继续处理您所在的列表。