Navigate / search

Decorating Immutable Christmas Trees

Download

This post is the fifth in the 2014 F# Advent Calendar series.

As much as I love having a real Christmas tree, I hate buying it and dragging it home. I hate decorating it. I hate taking it down again. Untangling lights, tinsel and baubles.

The problem with Christmas trees is that once you’ve decorated them, there’s no easy way to get back to the bare tree that you bought. You have to get in there and undo all the work.

An immutable tree sounds appealing.

“Sorry kids, we can’t decorate the tree. Don’t shoot the messenger, I don’t make the rules.”

That’s all fine until one of the kids discovers that if you do decorate the tree you get a new tree. “TWO TREES” they scream, then, “THREE TREES” and the whole thing descends into a Dr Seuss story.

How I learned to reject change and love immutability

Not too long ago if you asked me to create a data structure like a binary tree, it would be written in C# and it would look like this.

    class BinaryTree<T> where T : IComparable
    {
        public T Value { get; private set; }
        public BinaryTree Left { get; private set; }
        public BinaryTree Right { get; private set; }

        public BinaryTree(T value)
        {
            Value = value;
        }

        public void Add(T value)
        {
            if(value.CompareTo(Value) == -1)
                if(Left == null)
                    Left = new BinaryTree(value);
                else
                    Left.Add(value);
            else
                if (Right == null)
                    Right = new BinaryTree(value);
                else
                    Right.Add(value);
        }
    }

Notice that the Add method doesn’t return anything. It “changes” the tree. You use it like this:

    var t = new BinaryTree<int>(5);
    t.Add(3);
    t.Add(7);

Back then, creating immutable data structures seemed like more trouble than it was worth. I knew how to do it, but it was easier to convince myself that I had the discipline to not need immutability.

I still see that push back against immutability in many of my C# colleagues. They’re not wrong. If you look at software development through a C# or Java lens immutable data structures can seem like a bit of an indulgence.

The Path Of Least Resistance

The thing is, immutability is easy. The problems I had were down to the tools and the path of least resistance that they encouraged.

If you asked me to build a binary tree today it would be immutable unless there was a good reason for it not to be. A big part of that change is down to language choice and the switch to Functional Programming.

Here is the same data structure and functionality as the C# code above, but this is F#. There isn’t much extraneous code here. We are immutable by default.

module BinaryTree

type BinaryTree<'a> =
    | Tree of 'a * BinaryTree<'a> * BinaryTree<'a>
    | Empty

let rec add value tree =
    match tree with
    | Empty -> Tree(value, Empty, Empty)
    | Tree (x, left, right) when value < x ->
        Tree(x, add value left, right)
    | Tree (x, left, right) ->
        Tree(x, left, add value right)

With this implementation we can use our binary tree as follows

    let t = Empty
    let u = BinaryTree.add 5 t
    let v = BinaryTree.add 3 u

And t, u and v will each represent different trees.

The second argument of the add method is the tree to add to, so we can pipe the output of one call into another, as follows:

    let t = Empty
            |> BinaryTree.add 3
            |> BinaryTree.add 4
            |> BinaryTree.add 2

Immutable is Easy

Lets see how you add something to an immutable tree. The result of adding a value to a tree is always a new tree. That’s important so keep it in mind, we are all about creating new trees here.

If we have an empty tree and we want to add a number like 5 then it’s easy, the new tree has one node containing the value 5 and no sub-trees.

    | Empty -> Tree(value, Empty, Empty)

If we add a value to an existing tree, we have two possibilities. The new value is less than the root of the existing tree, or it isn’t. In both cases we create a new tree, but what will it look like?

In both cases the new and old tree will have the same root value. Remember the new value gets added to either the left or right sub-tree.

If the new value is less than the existing value, we add it to the left sub-tree. This means the right sub-tree will be the same as that of the original tree.

    | Tree (x, left, right) when value < x ->
        Tree(x, add value left, right)

Look at that. Create a new tree with the same value as the old tree, the same right sub-tree, and with the new value added on the left sub-tree.

Of course that’s a recursive call so it will compare the new value with whatever values exist down the left sub-tree.

The only remaining scenario is a new value that’s equal to or greater than the value in the existing value. As you might expect it’s the mirror of the previous case.

    | Tree (x, left, right) ->
        Tree(x, left, add value right)

As you can see with a handful of lines of code we not only get immutable binary trees but we get trees that share common nodes. The new tree doesn’t need to copy the unchanged sub-tree of the original, it can just point to it, safe in the knowledge that it is immutable.

Expressions vs Statements

Look again at the Add method in the F# example. All we have is a 1:1 mapping of conditions to expressions. The expressions evaluate to the new Trees.

Compare this with the nested if…else statements in the C# example.

The imperative (statement style) code describes how to change an existing tree. It uses a few nested questions. This kind of code requires you to keep your wits about you. How did I get here? What answers to what questions brought me to this line?

The functional (expression style) code is much simpler (in my opinion). There are three conditions that map 1:1 to expressions. Each expression produces a new tree.

We don’t write code that describes how to construct the new tree, or change the old one. We just construct the new Tree and we’re done.

Gifts Under The Tree

One aspect of Christmas Trees that I do like is the gifts. Here to finish are a few random snippets, questions, and ideas that relate to the F# code above.

Folding into a Tree

We can use the add method to create a BinaryTree by folding a collection, using an Empty tree as the starting point.

    let nums = [5; 8; 3; 5; 3; 7; 4; 8; 4; 7; 89; 4;]
    let t = List.fold(fun acc n->BinaryTree.add n acc) Empty nums

As an exercise, reverse the arguments in the definition of the Add method so it looks like this:

let rec add tree value =
    match tree with
    | Empty -> Tree(value, Empty, Empty)
    | Tree (x, left, right) when value < x ->
        Tree(x, add left value, right)
    | Tree (x, left, right) ->
        Tree(x, left, add right value)

With that done, how can we simplify the List.fold above?

What impact does that have on this earlier code:

    let t = Empty
            |> BinaryTree.add 3
            |> BinaryTree.add 4
            |> BinaryTree.add 2

Proper Decorations

What kind of tree has numbers or even strings? Let’s get some Tinsel, Lights and Baubles on there.

type Decoration =
    | Bauble
    | Lights
    | Tinsel

let decorations =
    [Tinsel; Lights; Bauble; Bauble; Tinsel; Bauble; Lights; Lights; Tinsel; Bauble; Bauble; Bauble]

let t = List.fold(fun acc n->BinaryTree.add n acc) Empty decorations

That will work, but the tree won’t look good. It segregates the different decorations into their own sections of the tree.

How could you create a tree that distributes the quantities of baubles, tinsel and lights evenly around the tree?

Removing A Node

Removing a node requires a little more thought than adding. Try and write an FSharp method to remove an item from a Tree. Here’s one approach.

Now try to write a remove method in the mutable C# BinaryTree. Which did you find easier? Was there any difference at all? Have you more confidence in one or the other?

Traversing The Tree

You can use a sequence expression to traverse a tree and output the results as sequence.

let rec inorder tree =
    seq {
      match tree with
          | Tree(x, left, right) ->
               yield! inorder left
               yield x
               yield! inorder right
          | Empty -> ()
    }

Note that calling inorder on the left and right sub-trees will produce sequences of their own. We use yield! to elevate those into the sequence we’re creating.

Duplicates

How would you you change the add method so that it throws away duplicate values rather than adding them to the tree? Go on, it’s easy.

This post is the fifth in the 2014 F# Advent Calendar series.