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}
             }))

Phillida

It looks to me like it's complaining that ::node isn't defined in the definitions of ::left, and ::right, so you may want to try defining ::node before those two. – Diamine

@Sam Estep: Then you would have the same problem, because ::node is defined in terms of ::left and ::right, which won't yet be defined. A circuit breaker is needed, like declare in Clojure. – Unmanned

@ChrisMurphy No, it works fine with ::left and ::right defined after ::node. See my answer for a pasted REPL session. – Baba

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

Spittle

I think of s/keys as saying that the value must be a map and it must contain certain keys; it's not the responsibility of s/keys to say anything about those keys - that's for the specs of those keys to worry about. Hence it's fine to include keys without specs in s/keys. Sorry I just said the words "specs" and "keys" an awful lot. – Blastopore

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}
             }))

Ferris

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.

Kathline