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:

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

 

Motivation

---

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:

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:

 

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:

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:

 

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:

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?):

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:

 

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:

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

 

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:

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

 

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.

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:

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

 

Conclusion

---

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.