A Binary Tree Zipper in C# by Mark Seemann
A port of another Haskell example, still just because.
This article is part of a series about Zippers. In this one, I port the Zipper data structure from the Learn You a Haskell for Great Good! article also called Zippers.
A word of warning: I'm assuming that you're familiar with the contents of that article, so I'll skip the pedagogical explanations; I can hardly do it better that it's done there. Additionally, I'll make heavy use of certain standard constructs to port Haskell code, most notably Church encoding to model sum types in languages that don't natively have them. Such as C#. In some cases, I'll implement the Church encoding using the data structure's catamorphism. Since the cyclomatic complexity of the resulting code is quite low, you may be able to follow what's going on even if you don't know what Church encoding or catamorphisms are, but if you want to understand the background and motivation for that style of programming, you can consult the cited resources.
The code shown in this article is available on GitHub.
Binary tree initialization and structure #
In the Haskell code, the binary Tree type is a recursive sum type, defined on a single line of code. C#, on the other hand, has no built-in language construct that supports sum types, so a more elaborate solution is required. At least two options are available to us. One is to model a sum type as a Visitor. Another is to use Church encoding. In this article, I'll do the latter.
I find the type name (Tree) used in the Zippers article a bit too vague, and since I consider explicit better than implicit, I'll use a more precise class name:
public sealed class BinaryTree<T>
Even so, there are different kinds of binary trees. In a previous article I've shown a catamorphism for a full binary tree. This variation is not as strict, since it allows a node to have zero, one, or two children. Or, strictly speaking, a node always has exactly two children, but both, or one of them, may be empty. BinaryTree<T> uses Church encoding to distinguish between the two, but we'll return to that in a moment.
First, we'll examine how the class allows initialization:
private readonly IBinaryTree root; private BinaryTree(IBinaryTree root) { this.root = root; } public BinaryTree() : this(Empty.Instance) { } public BinaryTree(T value, BinaryTree<T> left, BinaryTree<T> right) : this(new Node(value, left.root, right.root)) { }
The class uses a private root object to implement behaviour, and constructor chaining for initialization. The master constructor is private, since the IBinaryTree interface is private. The parameterless constructor implicitly indicates an empty node, whereas the other public constructor indicates a node with a value and two children. Yes, I know that I just wrote that explicit is better than implicit, but it turns out that with the target-typed new operator feature in C#, constructing trees in code becomes easier with this design choice:
BinaryTree<int> sut = new( 42, new(), new(2, new(), new()));
As the variable name suggests, I've taken this code example from a unit test.
Private interface #
The class delegates method calls to the root field, which is an instance of the private, nested IBinaryTree interface:
private interface IBinaryTree { TResult Aggregate<TResult>( Func<TResult> whenEmpty, Func<T, TResult, TResult, TResult> whenNode); }
Why is IBinaryTree a private interface? Why does that interface even exist?
To be frank, I could have chosen another implementation strategy. Since there's only two mutually exclusive alternatives (node or empty), I could also have indicated which is which with a Boolean flag. You can see an example of that implementation tactic in the Table class in the sample code that accompanies Code That Fits in Your Head.
Using a Boolean flag, however, only works when there are exactly two choices. If you have three or more, things because more complicated. You could try to use an enum, but in most languages, these tend to be nothing but glorified integers, and are typically not type-safe. If you define a three-way enum, there's no guarantee that a value of that type takes only one of these three values, and a good compiler will typically insist that you check for any other value as well. The C# compiler certainly does.
Church encoding offers a better alternative, but since it makes use of polymorphism, the most idiomatic choice in C# is either an interface or a base class. Since I favour interfaces over base classes, that's what I've chosen here, but for the purposes of this little digression, it makes no difference: The following argument applies to base classes as well.
An interface (or base class) suggests to users of an API that they can implement it in order to extend behaviour. That's an impression I don't wish to give client developers. The purpose of the interface is exclusively to enable double dispatch to work. There's only two implementations of the IBinaryTree interface, and under no circumstances should there be more.
The interface is an implementation detail, which is why both it, and its implementations, are private.
Binary tree catamorphism #
The IBinaryTree interface defines a catamorphism for the BinaryTree<T> class. Since we may often view a catamorphism as a sort of 'generalized fold', and since these kinds of operations in C# are typically called Aggregate, that's what I've called the method.
An aggregate function affords a way to traverse a data structure and collect information into a single value, here of type TResult. The return type may, however, be a complex type, including another BinaryTree<T>. You'll see examples of complex return values later in this article.
As already discussed, there are exactly two implementations of IBinaryTree. The one representing an empty node is the simplest:
private sealed class Empty : IBinaryTree { public readonly static Empty Instance = new(); private Empty() { } public TResult Aggregate<TResult>( Func<TResult> whenEmpty, Func<T, TResult, TResult, TResult> whenNode) { return whenEmpty(); } }
The Aggregate implementation unconditionally calls the supplied whenEmpty function, which returns some TResult value unknown to the Empty class.
Although not strictly necessary, I've made the class a Singleton. Since I like to take advantage of structural equality to write better tests, it was either that, or overriding Equals and GetHashCode.
The other implementation gets around that problem by being a record:
private sealed record Node(T Value, IBinaryTree Left, IBinaryTree Right) : IBinaryTree { public TResult Aggregate<TResult>( Func<TResult> whenEmpty, Func<T, TResult, TResult, TResult> whenNode) { return whenNode( Value, Left.Aggregate(whenEmpty, whenNode), Right.Aggregate(whenEmpty, whenNode)); } }
It, too, unconditionally calls one of the two functions passed to its Aggregate method, but this time whenNode. It does that, however, by first recursively calling Aggregate on both Left and Right. It needs to do that because the whenNode function expects the subtrees to have been already converted to values of the TResult return type. This is a common pattern with catamorphisms, and takes a bit of time getting used to. You can see similar examples in the articles Tree catamorphism, Rose tree catamorphism, and Full binary tree catamorphism.
The BinaryTree<T> class defines a public Aggregate method that delegates to its root field:
public TResult Aggregate<TResult>( Func<TResult> whenEmpty, Func<T, TResult, TResult, TResult> whenNode) { return root.Aggregate(whenEmpty, whenNode); }
The astute reader may now remark that the Aggregate method doesn't look like a Church encoding.
Binary tree Church encoding #
A Church encoding will typically have a Match method that enables client code to match on all the alternative cases in the sum type, without those confusing already-converted TResult values. It turns out that you can implement the desired Match method with the Aggregate method.
One of the advantages of doing meaningless coding exercises like this one is that you can pursue various ideas that interest you. One idea that interests me is the potential universality of catamorphisms. I conjecture that a catamorphism is an algebraic data type's universal API, and that you can implement all other methods or functions with it. I admit that I haven't done much research in the form of perusing existing literature, but at least it seems to be the case conspicuously often.
As it is here.
public TResult Match<TResult>( Func<TResult> whenEmpty, Func<T, BinaryTree<T>, BinaryTree<T>, TResult> whenNode) { return root .Aggregate( () => (tree: new BinaryTree<T>(), result: whenEmpty()), (x, l, r) => ( new BinaryTree<T>(x, l.tree, r.tree), whenNode(x, l.tree, r.tree))) .result; }
Now, I readily admit that it took me a couple of hours tossing and turning in my bed before this solution came to me. I don't find it intuitive at all, but it works.
The Aggregate method requires that the whenNode function's left and right values are of the same TResult type as the return type. How do we consolidate that requirement with the Match method's variation, where its whenNode function requires the left and right values to be BinaryTree<T> values, but the return type still TResult?
The way out of this conundrum, it turns out, is to combine both in a tuple. Thus, when Match calls Aggregate, the implied TResult type is not the TResult visible in the Match method declaration. Rather, it's inferred to be of the type (BinaryTree<T>, TResult). That is, a tuple where the first element is a BinaryTree<T> value, and the second element is a TResult value. The C# compiler's type inference engine then figures out that (BinaryTree<T>, TResult) must also be the return type of the Aggregate method call.
That's not what Match should return, but the second tuple element contains a value of the correct type, so it returns that. Since I've given the tuple elements names, the Match implementation accomplishes that by returning the result tuple field.
Breadcrumbs #
That's just the tree that we want to zip. So far, we can only move from root to branches, but not the other way. Before we can define a Zipper for the tree, we need a data structure to store breadcrumbs (the navigation log, if you will).
In Haskell it's just another one-liner, but in C# this requires another full-fledged class:
public sealed class Crumb<T>
It's another sum type, so once more, I make the constructor private and use a private class field for the implementation:
private readonly ICrumb imp; private Crumb(ICrumb imp) { this.imp = imp; } internal static Crumb<T> Left(T value, BinaryTree<T> right) { return new(new LeftCrumb(value, right)); } internal static Crumb<T> Right(T value, BinaryTree<T> left) { return new(new RightCrumb(value, left)); }
To stay consistent throughout the code base, I also use Church encoding to distinguish between a Left and Right breadcrumb, and the technique is similar. First, define a private interface:
private interface ICrumb { TResult Match<TResult>( Func<T, BinaryTree<T>, TResult> whenLeft, Func<T, BinaryTree<T>, TResult> whenRight); }
Then, use private nested types to implement the interface.
private sealed record LeftCrumb(T Value, BinaryTree<T> Right) : ICrumb { public TResult Match<TResult>( Func<T, BinaryTree<T>, TResult> whenLeft, Func<T, BinaryTree<T>, TResult> whenRight) { return whenLeft(Value, Right); } }
The RightCrumb record is essentially just the 'mirror image' of the LeftCrumb record, and just as was the case with BinaryTree<T>, the Crumb<T> class exposes an externally accessible Match method that just delegates to the private class field:
public TResult Match<TResult>( Func<T, BinaryTree<T>, TResult> whenLeft, Func<T, BinaryTree<T>, TResult> whenRight) { return imp.Match(whenLeft, whenRight); }
Finally, all the building blocks are ready for the actual Zipper.
Zipper data structure and initialization #
In the Haskell code, the Zipper is another one-liner, and really just a type alias. In C#, once more, we're going to need a full class.
public sealed class BinaryTreeZipper<T>
The Haskell article simply calls this type alias Zipper, but I find that name too general, since there's more than one kind of Zipper. I think I understand that the article chooses that name for didactic reasons, but here I've chosen a more consistent disambiguation scheme, so I've named the class BinaryTreeZipper<T>.
The Haskell example is just a type alias for a tuple, and the C# class is similar, although with significantly more ceremony:
public BinaryTree<T> Tree { get; } public IEnumerable<Crumb<T>> Breadcrumbs { get; } private BinaryTreeZipper( BinaryTree<T> tree, IEnumerable<Crumb<T>> breadcrumbs) { Tree = tree; Breadcrumbs = breadcrumbs; } public BinaryTreeZipper(BinaryTree<T> tree) : this(tree, []) { }
I've here chosen to add an extra bit of encapsulation by making the master constructor private. This prevents client code from creating an arbitrary object with breadcrumbs without having navigated through the tree. To be honest, I don't think it violates any contract even if we allow this, but it at least highlights that the Breadcrumbs role is to keep a log of what previously happened to the object.
Navigation #
We can now reproduce the navigation functions from the Haskell article.
public BinaryTreeZipper<T>? GoLeft() { return Tree.Match<BinaryTreeZipper<T>?>( whenEmpty: () => null, whenNode: (x, l, r) => new BinaryTreeZipper<T>( l, Breadcrumbs.Prepend(Crumb.Left(x, r)))); }
Going left 'pattern-matches' on the Tree and, if not empty, constructs a new BinaryTreeZipper object with the left tree, and a Left breadcrumb that stores the 'current' node value and the right subtree. If the 'current' node is empty, on the other hand, the method returns null. This possibility is explicitly indicated by the BinaryTreeZipper<T>? return type; notice the question mark, which indicates that the value may be null. If you're working in a context or language where that feature isn't available, you may instead consider taking advantage of the Maybe monad (which is also what you'd idiomatically do in Haskell).
The GoRight method is similar to GoLeft.
We may also attempt to navigate up in the tree, undoing our last downward move:
public BinaryTreeZipper<T>? GoUp() { if (!Breadcrumbs.Any()) return null; var head = Breadcrumbs.First(); var tail = Breadcrumbs.Skip(1); return head.Match( whenLeft: (x, r) => new BinaryTreeZipper<T>( new BinaryTree<T>(x, Tree, r), tail), whenRight: (x, l) => new BinaryTreeZipper<T>( new BinaryTree<T>(x, l, Tree), tail)); }
This is another operation that may fail. If we're already at the root of the tree, there are no Breadcrumbs, in which case the only option is to return a value indicating that the operation failed; here, null, but in other languages perhaps None or Nothing.
If, on the other hand, there's at least one breadcrumb, the GoUp method uses the most recent one (head) to construct a new BinaryTreeZipper<T> object that reconstitutes the opposite (sibling) subtree and the parent node. It does that by 'pattern-matching' on the head breadcrumb, which enables it to distinguish a left breadcrumb from a right breadcrumb.
Finally, we may keep trying to GoUp until we reach the root:
public BinaryTreeZipper<T> TopMost() { return GoUp()?.TopMost() ?? this; }
You'll see an example of that a little later.
Modifications #
Continuing the port of the Haskell code, we can Modify the current node with a function:
public BinaryTreeZipper<T> Modify(Func<T, T> f) { return new BinaryTreeZipper<T>( Tree.Match( whenEmpty: () => new BinaryTree<T>(), whenNode: (x, l, r) => new BinaryTree<T>(f(x), l, r)), Breadcrumbs); }
This operation always succeeds, since it chooses to ignore the change if the tree is empty. Thus, there's no question mark on the return type, indicating that the method never returns null.
Finally, we may replace a node with a new subtree:
public BinaryTreeZipper<T> Attach(BinaryTree<T> tree) { return new BinaryTreeZipper<T>(tree, Breadcrumbs); }
The following unit test demonstrates a combination of several of the methods shown above:
[Fact] public void AttachAndGoTopMost() { var sut = new BinaryTreeZipper<char>(freeTree); var farLeft = sut.GoLeft()?.GoLeft()?.GoLeft()?.GoLeft(); var actual = farLeft?.Attach(new('Z', new(), new())).TopMost(); Assert.NotNull(actual); Assert.Equal( new('P', new('O', new('L', new('N', new('Z', new(), new()), new()), new('T', new(), new())), new('Y', new('S', new(), new()), new('A', new(), new()))), new('L', new('W', new('C', new(), new()), new('R', new(), new())), new('A', new('A', new(), new()), new('C', new(), new())))), actual.Tree); Assert.Empty(actual.Breadcrumbs); }
The test starts with freeTree (not shown) and first navigates to the leftmost empty node. Here it uses Attach to add a new 'singleton' subtree with the value 'Z'. Finally, it uses TopMost to return to the root node.
In the Assert phase, the test verifies that the actual object contains the expected values.
Conclusion #
The Tree Zipper shown here is a port of the example given in the Haskell Zippers article. As I've already discussed in the introduction article, this data structure doesn't make much sense in C#, where you can easily implement a navigable tree with two-way links. Even if this requires state mutation, you can package such a data structure in a proper object with good encapsulation, so that operations don't leave any dangling pointers or the like.
As far as I can tell, the code shown in this article isn't useful in production code, but I hope that, at least, you still learned something from it. I always learn a new thing or two from doing programming exercises and writing about them, and this was no exception.
In the next article, I continue with the final of the Haskell article's three examples.
Next: FSZipper in C#.
