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.
Setup
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:
defmodule Tree do
def leaf(v), do: { :leaf, v }
def branch(left, right), do: { :branch, left, right }
end
In the test I used the nested calls to these constructors build a tree to use in the tests:
defmodule TreesTest do
use ExUnit.Case
def build_tree do
Tree.branch(
Tree.branch(
Tree.branch(
Tree.leaf(6),
Tree.branch(
Tree.leaf(5),
Tree.leaf(4)
)
),
Tree.leaf(3)
),
Tree.branch(
Tree.branch(
Tree.branch(
Tree.leaf(2),
Tree.leaf(1)
),
Tree.leaf(0)
),
Tree.leaf(0)
)
)
end
Which is intended to represent the following tree:
Inspect
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:
{:branch,
{:branch, {:branch, {:leaf, 6}, {:branch, {:leaf, 5}, {:leaf, 4}}},
{:leaf, 3}},
{:branch, {:branch, {:branch, {:leaf, 2}, {:leaf, 1}}, {:leaf, 0}},
{:leaf, 0}}}
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 tree_size
and maximum
functions:
def tree_size({:leaf, _}), do: 1
def tree_size({:branch, left, right}), do: 1 + tree_size(left) + tree_size(right)
def maximum({:leaf, v}), do: v
def maximum({:branch, left, right}), do: max(maximum(left), maximum(right))
These are simple pattern matching, recursive functions. tree_size
counts the
nodes and maximum
uses 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:
def fold({:leaf, v}, leaf_func, _branch_func) do
leaf_func.(v)
end
def fold({:branch, left, right}, leaf_func, branch_func) do
branch_func.(fold(left, leaf_func, branch_func),
fold(right, leaf_func, branch_func))
end
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 tree_size
and maximum
using fold:
def size_with_fold(t), do: fold(t,
fn(_v) -> 1 end,
fn(left_acc, right_acc) -> 1 + left_acc + right_acc end
)
def max_with_fold(t), do: fold(t,
fn(v) -> v end,
fn(left_acc, right_acc) -> max(left_acc, right_acc) end
)
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.