递归定义的数据结构中节点之间依赖关系的 Clojure 规范

Question

是否有规范或惯用的方式来编写递归定义的数据结构中节点值之间依赖关系的规范？

作为一个最小的例子，假设我想将一个排序列表存储为一个嵌套向量，其中每个“节点”是一个值和列表的尾部：

 [1 [2 [3 [4 nil]]]]

可以编写列表本身结构的规范

(s/def ::node (s/or :empty nil?
                    :list (s/cat :value number? :tail ::node)))

但是，当我想添加订购要求时，我找不到好的方法正在写。

直白的写法感觉有点笨拙。作为符合 :tail 的值是一个 MapEntry，我不能使用像 (get-in % [:tail :list :value]) 这样的东西（我可以把它写成 (get-in % [:tail 1 :value]) 但那个硬编码的索引感觉太脆弱了），但必须穿过 (val):

(s/def ::node (s/or :empty nil?
                     :list (s/& (s/cat :value number? :tail ::node)
                                #(or (= (-> % :tail key) :empty) 
                                         (< (:value %) (-> % :tail val :value))) 
                                )))

这个有效：

(s/conform ::node nil)  ; [:empty nil]
(s/conform ::node [1 nil ] ) ; [:list {:value 1, :tail [:empty nil]}]
(s/explain ::node [4 [1 nil]] )
  ; {:value 4, :tail [:list {:value 1, :tail [:empty nil]}]} - failed: 
  ; (or (= (-> % :tail key) :empty) (< (:value %) (-> % :tail val 
  ; :value))) in: [1] at: [:list] spec: :spec-test.core/node
  ; [4 [1 nil]] - failed: nil? at: [:empty] spec: :spec-test.core/node

(s/conform ::node [1 [4 nil]] )  ; [:list {:value 1, :tail [:list {:value 4, :tail [:empty nil]}]}]
(s/conform ::node [1 [2 [4 nil]]] )
  ; [:list
  ; {:value 1,
  ;  :tail
  ;  [:list {:value 2, :tail [:list {:value 4, :tail [:empty nil]}]}]}]

或者，我可以使用多规格来制作 ::node 的规格更清楚一点：

(s/def ::node (s/or :empty nil?
                    :list (s/& (s/cat :value number? :tail ::node)
                               (s/multi-spec empty-or-increasing :ignored) 
                               )))

这也允许我分离出 :empty 分支，但它仍然存在获取 :tail 的（头）值的问题：

(defmulti empty-or-increasing #(-> % :tail key))
(defmethod empty-or-increasing :empty
  [_]
  (fn[x] true))
(defmethod empty-or-increasing :default
  [_]
  #(do (< (:value %) (-> % :tail val :value)))
  )

有没有办法获取 :tail 节点的 :value 而不必用 #(-> % :tail val :value) 提取 MapEntry 的 val 部分或 #(get-in % [:tail 1 :value])?

Answer 1

您可以使用 s/conformer 来代替 MapEntry 获取地图。

(s/def ::node (s/and (s/or :empty nil?
                           :list (s/& (s/cat :value number? :tail ::node)
                                      (fn [x]
                                          (or (-> x :tail (contains? :empty))
                                              (-> x :tail :list :value (> (:value x)))))))
                     (s/conformer (fn [x] (into {} [x])))))

结果看起来更一致：

(s/conform ::node [1 [2 [4 nil]]])

=> {:list {:value 1, :tail {:list {:value 2, :tail {:list {:value 4, :tail {:empty nil}}}}}}}

递归定义的数据结构中节点之间依赖关系的 Clojure 规范

Clojure spec for dependencies between nodes in a recursively defined data structure

clojure

destructuring

clojure.spec