Recursive entity spec

Question

I haven't found any example of how to do a recursive entity spec like I'm attempting below. I realize that the ::left and ::right are failing because they aren't defined yet, so I'm wondering how I can define them recursively in the ::node spec.

(s/def ::key string?)
(s/def ::value string?)
(s/def ::left ::node)
(s/def ::right ::node)
(s/def ::n int?)
(s/def ::node (s/keys :req [::key ::value ::n]
                      :opt [::left ::right]))

(defn test-it []
  (s/valid? ::node
            {::key "hi"
             ::value "bye"
             ::n 0
             ::left {::key "what"
                     ::value "nothing"
                     ::n 0}
             ::right {::key "hello"
                      ::value "goodbye"
                      ::n 0}
             }))

Answer 1

It works if you move ::left and ::right definitions to below ::node, as suggested by Sam Estep in a comment on the question; the references in s/keys won't be immediately followed:

Clojure 1.9.0-alpha14
user=> (require '[clojure.spec :as s])
nil
user=> (s/def ::key string?)
:user/key
user=> (s/def ::value string?)
:user/value
user=> (s/def ::n int?)
:user/n
(s/def ::node (s/keys :req [::key ::value ::n]
                      :opt [::left ::right]))
:user/node
user=> (s/def ::left ::node)
:user/left
user=> (s/def ::right ::node)
:user/right
(defn test-it []
  (s/valid? ::node
            {::key "hi"
             ::value "bye"
             ::n 0
             ::left {::key "what"
                     ::value "nothing"
                     ::n 0}
             ::right {::key "hello"
                      ::value "goodbye"
                      ::n 0}
             }))
#'user/test-it
user=> (test-it)
true
user=> (s/valid? ::node {::key "hi" ::value "bye" ::n 0 ::left {}})
false

Answer 2

Unlike regular defs, s/defs are not dependent on the order of declaration... except when you alias (s/def ::a ::b) where ::b must be defined before ::a.

So either you reorder your s/defs as suggested by Michał or you wrap the right-hand value in (s/and):

(s/def ::key string?)
(s/def ::value string?)
(s/def ::left (s/and ::node))
(s/def ::right (s/and ::node))
(s/def ::n int?)
(s/def ::node (s/keys :req [::key ::value ::n]
                      :opt [::left ::right]))

(defn test-it []
  (s/valid? ::node
            {::key "hi"
             ::value "bye"
             ::n 0
             ::left {::key "what"
                     ::value "nothing"
                     ::n 0}
             ::right {::key "hello"
                      ::value "goodbye"
                      ::n 0}
             }))

Answer 3

What you have are not left and right entities, but two nodes defined in an identical way, and unfortunately you can't have two keys with the same name in the map, since spec does not allow "aliasing" of a keyword to a spec, but instead uses the keyword itself to identify the spec.

One option, if you are willing, is to define the left and right nodes in terms of a single ::children key, which is a collection of (one or) two ::nodes.

(s/def ::key string?)
(s/def ::value string?)
(s/def ::n int?)

(s/def ::node (s/keys :req [::key ::value ::n]))
(s/def ::children (s/coll-of ::node :count 2))
;; for 1 or 2 children:   (s/coll-of ::node :min-count 1 :max-count 2)

(s/valid? ::node
  {::key "parent-1" ::value "parent-1" ::n 1
   ::children [{::key "leaf-1" ::value "leaf-1" ::n 2}
               {::key "parent-2" ::value "parent-2" ::n 3
                ::children [{::key "leaf-2" ::value "leaf-2" ::n 4}
                            {::key "leaf-3" ::value "leaf-3" ::n 5}]}]})

This gives you a similar structure, with the slight additional complexity of a vector containing two nodes, instead of two keys, each with a node.

Another option that allows for a definition purely in terms of itself is to forego a map structure, and do a nested vector instead:

(s/def ::node (s/or :parent (s/coll-of ::node :count 2)
                    :leaf (s/tuple ::key ::value ::n)))

(s/valid? ::node
  [[[["a" "a" 1]
     ["b" "b" 2]]
    ["c" "c" 3]]
   ["d" "d" 4]])

This works because the elements are sequential and need not be associated with a unique key, as in the map structure above (yes, vectors are associative also, but their sequential nature is being used in this case). This is admittedly not as "clean," and the first method is probably preferred, but it is an option if you're willing to forego the associative structure and trade it for a sequential one.