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

Question

Is there a canonical or idiomatic way of writing a spec for dependencies between the values in nodes in a recursively defined data structure?

As a minimal example, let's say I want to store a sorted list as a nested vector where each "node" is a value and the tail of the list:

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

The spec for the structure of the list itself can be written

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

However, when I want to add the ordering requirement I cannot find a good way of writing it.

The straight-forward way of writing it feels a bit clumsy. As the conformed value of :tail is a MapEntry, I cannot use something like (get-in % [:tail :list :value]) (I could write it as (get-in % [:tail 1 :value]) but that hard-coded index feels too brittle), but have to thread it through (val):

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

This works:

(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]}]}]}]

Alternatively, I can use a multi-spec to make the spec for ::node a bit clearer:

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

That also allows me to separate out the :empty branch but it still has the problem of getting the value of the (head of the) :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)))
  )

Is there a way to get the :value of the :tail node without having to extract the val part of the MapEntry with #(-> % :tail val :value) or #(get-in % [:tail 1 :value])?

Answer 1

You could use s/conformer in order to get a map in lieu of a 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])))))

and the result will look somewhat more consistent:

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

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