Recursive Schemas

Many data structures are defined inductively, and if we want to write schemas to match them, we will require recursive schema definitions.

As an example, let's consider a binary tree The standard definition of a binary tree is inductive. Each node in a binary tree of longs must be one of the following:

• an empty node
• a node containing a long value, a left and right subtree, where each of these substrees is itself a binary tree

The recursive schema type can be used to naturally capture this inductive definition:

(def BinaryTree 
  (maybe ;; any empty binary tree is represented by nil
   {:value long 
    :left (recursive #'BinaryTree) 
    :right (recursive #'BinaryTree)}))

Here we are defining a new composite, recursive schema for a binary tree. The schema is recursive because the definition refers to itself. At its root, the binary tree is implemented using Maybe, which validates against nil or the passed in schema. The nil case corresponds to an empty binary tree node, and the non-nil case is a map with keys corresponding to the various parts of the binary tree: value, left, and right subtrees. Note that in order to recursively refer to the definition of BinaryTree we had to use the recursive constructor and quote the var using #'.

We can check that the BinaryTree schema matches the data that we expect:

(check BinaryTree nil)
> nil 

(check BinaryTree {:value 4 :right {:value 2 :left nil :right nil} :left nil})
> nil 

When the data doesn't match the schema, the errors we get are informative about which parts are incorrect:

(check BinaryTree {:value 4 :left nil})
> {:right missing-required-key}

(check BinaryTree {:value "Hello" :right nil :left nil})
> {:value (not (instance? java.lang.Long "Hello"))}

Recursion is a powerful technique that allows a small schema to succinctly describe an infinite set of arbitrary large data structures.