"Write a predicate tree? that succeeds if and only if its argument is representing a binary tree."
Example/Test
(deftest nil-is-a-tree (is (= true (tree? nil))))
Discussion
This is an interesting problem because it allows us to touch the basic question of static vs. dynamic typing.
If we look at the Scala solution, we see that in a statically typed language this problem can be fully solved via the type system. Or as Phil Gold put it: "Score one for static typing."
I am not a zealot when it comes to static vs. dynamic typing. Both approaches have their merits. There are many ways to look at this (prototyping, easier code reuse vs. working with legacy code, catching errors early ...). Maybe it is a very narrow perspective but for me it is almost more of a social than a technical issue. I see how a team of developers with mixed skill levels in combination with a code base in various stages of decay can benefit from a compiler giving them more guidance along the way through the maze. On the other hand, I have never missed the absence of a strict type system in Clojure when quickly building prototypes or solving programming problems. While I am still on the fence about the general issue of static vs. dynamic type systems, let us look at the problem at hand: working with binary trees.
The Dynamic Approach
We can solve this problem in a "dynamic" fashion building upon what we have done so far in this series. We worked with trees before for problem 25 using a library called core.match, which gives us pattern matching in Clojure to implement all the tree operations.
With core.match we get the tree?-predicate with a simple three way pattern match: it is either a node consisting of a label and two subtrees or nil representing the empty tree. Everything else is not a tree. The only complication is that we need to apply the pattern match for the node recursively, because the left and right subtrees should also be proper trees. Luckily, core.match supports function application in match expressions since 0.3.0.
Have a look at the solution and the accompanying tests to the get the idea.
Best of Both Worlds?
In Clojure we have a second option because, while being dynamic as a language, it offers us optional static typing in the form of a library called core.typed. The library is the result of the work Ambrose Bonnaire-Sergeant did for his PhD dissertation.
It allows us to declare a type Node consisting of a label of any kind and two children that are trees themselves. A tree is now either an empty tree (represented by nil) or one of these nodes.
(t/ann-datatype Node [val :- Any
l :- Tree
r :- Tree])
(deftype Node [val l r])
(t/defalias Tree
(t/Nilable Node))
To make this work, all you have to do is include core.typed as a library dependency in your project.clj (assuming you are using leiningen as your build tool). The type checking is not part of the compilation but an extra step you have to integrate into your workflow. Editor integrations for vim, Emacs and LightTable make it easier to construct your type system during development.
It helps to look at the core.typed example code (even if you are familiar with static typing) to work out how to apply the type annotations.
