A Clojure.Spec for Generic Binary Trees

Back in the post on a previous post Clojure Spec, we discussed how to correctly spec a binary tree using Clojure.Spec. Among the many possible representations for binary trees in Clojure, we chose the following one:

  • A node is a vector containing a value followed by a map of children
  • Inside the map of children:
    • The :left key will be associated the left tree
    • The :right key will be associated the right tree

Here is an example of such a binary tree:

(def sample-tree
{:left [2 {}]
:right [3
{:left [4 {}]
:right [5 {}]}]

The challenge is to come up with a clojure.spec to validate a binary tree while making sure that each value of the binary tree obeys a predicate provided by the user (such as int? in our specific example).



My original motivation was to express something like the following generic binary tree in Java, where each node has children holding values of the same type:

class BinaryTree<A>
A value;
BinaryTree<A> left;
BinaryTree<A> right;
view raw BinaryTree.java hosted with ❤ by GitHub

Where A is a type parameter. A BinaryTree of Integer would only be allowed to contain integers and would not be allowed to contain a String for instance. I was curious how I could check such a property using Clojure.Spec.


Best attempts so far

In our previous post on the subject, we came with the following spec for integer binary trees, using map-of for the children:

(s/def ::good-binary-tree
:value int?
:children (s/map-of #{:left :right} ::good-binary-tree)))


Generalizing to any tree

We observe that the only moving parts of this spec are the name of the spec and the predicate on the value conformance. This means we can easily generate this spec to work for any kind of binary trees, using the following macro:

(defmacro def-b-tree
[name pred]
`(s/def ~name
:value ~pred
(s/map-of #{:left :right} ~name))))
view raw def-b-tree.clj hosted with ❤ by GitHub

Using this macro, we can create specification for binary tree of specific types quite easily. We show below how to get back our integer binary tree:

(def-b-tree ::int-binary-tree int?)
(s/valid? ::int-binary-tree sample-tree)
; => true


Remaining problems

But this macro is not very satisfying. This solution forces us to define a dedicated global name for each kind of binary tree we want to describe:

(def-b-tree ::int-b-tree int?)
(def-b-tree ::string-b-tree string?)
; And so on...

We would prefer something that would allow us to create un-named specs that we could compose into bigger spec, much like coll-of does for collection for integers.


A better solution

In the Paris Clojure Meetup held the 17 of May 2017, I gave a presentation on Clojure.Spec whose slides are available here. This challenge was shown to the attendees. Although we could not find a solution during the evening, the discussions that followed the presentation led me to a much better solution.


Decouple shape and value conformance

The trick is to decouple the specification of the shape of the tree from the specification of its content. The recursive nature of the binary tree makes it hard to check both at the same time using spec. The good news is that specs can be composed with s/and.

We can first check the shape of the tree, with the following spec that does not concern itself with the conformance of the values (it uses any?):

(s/def ::binary-tree-impl
:value any?
(s/map-of #{:left :right} ::binary-tree-impl)))

We can independently check the conformance of the values. To do so, we collect all the values of the tree with a depth first search, and call every on the resulting collection. Here is how it would look for an integer binary tree:

(s/def ::int-binary-tree
#(every? int? (dfs-binary-tree %))


Generalizing to any tree

The definition of the specification of ::int-binary-tree is no longer recursive. So the only moving part is the predicate on the values of the tree.

We can therefore write a macro that looks like coll-of but for binary trees, named binary-tree-of. It accepts a predicate that applies on the values of the tree:

(defmacro binary-tree-of
#(every? ~pred (dfs-binary-tree %))

Using this macro, we can create a binary tree specification on the fly, without having to use a global name:

(s/valid? (binary-tree-of int?) sample-tree)
; => true
(s/valid? (binary-tree-of string?) sample-tree)
; => false


Do you like trees in trees?

We can even compose our specification of binary trees recursively, and write a specification for binary trees of binary trees of integers:

(binary-tree-of (binary-tree-of any?))
[sample-tree {}])

This requires to improve our definition of binary-tree-of to support nested specs, by wrapping our predicate with s/valid?:

(defmacro binary-tree-of
#(every? (partial s/valid? ~pred) (dfs-binary-tree %))


Remaining issues

There is still an issue with the specification as we wrote it. In case the value is not conforming, we do a depth first search before having validated the binary tree shape. This can be solved by inverting the arguments of s/and.

(defmacro binary-tree-of
#(every? (partial s/valid? ~pred) (dfs-binary-tree %))

Try it, and you will see it fails. The argument provided to our depth first search will become the conformed argument from ::binary-tree-impl. We can wrap this sub-spec with s/valid? to make it a predicate and remove the conformance:

(defmacro binary-tree-of
#(s/valid? ::binary-tree-impl %)
#(every? (partial s/valid? ~pred) (dfs-binary-tree %))

This shows us that s/and is sensitive to ordering of its different arguments. I found this quite surprising.



There is nothing like showing a problem we could not solve to others. It helps getting rid of a fixed idea that prevents us from seeing the solution.

Proper decomposition makes the hardest problem go away. Clojure.Spec allows to compose spec so that we can separate things such as structural conformance from the conformance of the values that appears in this structure.

I hope you found this exercise entertaining as I did. It shows how non-obvious it is (for someone accustomed to static type systems) to use something as different as Clojure.Spec and how far it goes it terms of expressivity.

Follow me on Twitter at @quduval.

Comments are closed.

Create a website or blog at WordPress.com

Up ↑

%d bloggers like this: