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])
?
You could use
s/conformer
in order to get a map in lieu of a MapEntry.and the result will look somewhat more consistent: