Last week I finished my series on list processing by working through the exercises in 3.4 of Functional Programming in Scala. This week I’ve continued with the exercises in section 3.5 which build up a set of operations to be performed on binary trees.
I’ve uploaded my tests and exercises to github. If you want to work through the exercises for yourself, then I recommend you grab the tests from the github repo now and work through them before reading the rest of this post.
Setting up the tree constructors is a bit different than the Scala example. I choose to use tuples to store the nodes rather than match against class. with I used an atom for the the first element the tuple to describes the type of node (:branch or :leaf). This made the matching easy and seems more inline with Elixir convention. Here are my constructors:
In the test I used the nested calls to these constructors build a tree to use in the tests:
Which is intended to represent the following tree:
While working out the constructors I finally learned the importance of IO.inspect/2. It was able to print out a description of my
IO.inspect/2 was quite helpful when working out how to build the data structure and get the constructors setup. It can print out a full description of the tree. Here’s the description for the tree show above:
Basic Tree Functions
The text starts off with exercises describing some simple tree exercises. Again, the text gives specific exercises and asks us to generalize them to higher order functions in the next step.
As examples, here are my
These are simple pattern matching, recursive functions.
tree_size counts the
max over all the nodes.
Higher Order Tree Functions
I had a bit of a false start implementing a fold over the tree. At first,
I had thought that the
maximum function had to maintain an accumulator and
I tried to generalized this into my fold function. This proved to be quite
difficult since when processing a leaf there would be two accumulated values
(one from the left and one from the right). Also, it wasn’t clear what the
initial value should be at the leaves. Should all leaves use the same initial
value or different values?
I finally realized that the
maximum function doesn’t need an accumulator and
I removed this from my fold function. Here’s the function:
I implemented fold using pattern matching with one version for the leaves and a sperate, recursive, version for the branch. I also realized that caller needed to be able to provide two functions, again one for the leaves and another for the branches.
Rewrite the Basic Tree Functions
Now that we’ve generalized these tree operations into a higher order fold
function the text recommends that we rewrite the basic functions using fold.
Here are my versions of
maximum using fold:
This was a pretty straightforward rewrite. I extracted out the leaf and branch functionality and passed it in as fold’s leaf_func and branch_func.