So far, we have seen how to use functions to work with or transform, other functions, to process data structures, or to create data types. Let's then finish this chapter by showing how a function can actually implement a data type by itself, becoming a sort of container of its own. In fact, this is a basic theoretical point of the lambda calculus (and if you want to learn more, look up Church Encoding and Scott Encoding), so we might very well say that we have come around to the point where we began this book, at the origins of Functional Programming!
Consider a binary tree. Such a tree may either be empty, or consist of a node (the tree root) with two sons: a left binary tree, and a right one.
Note
In Chapter 9, Designing Functions - Recursion, we worked with more general tree structures, such as a filesystem or the browser DOM itself, which allow a node to have any number of sons. In the particular case of the trees we are working with in...