A Tree functor by Mark Seemann
A generalised tree object as a functor. Another functor example for object-oriented programmers.
This article is an instalment in an article series about functors. In a previous article, you saw how to implement the Maybe functor in C#. In this article, you'll get another functor example: a generalised tree (also known as a rose tree).
As opposed to a binary tree, any node in a generalised tree can have an arbitrary number of children, including none.
Implementation #
The following Tree<T> class can contain objects of the generic type T. Being generic, it's a candidate for a functor, and it does, in fact, turn out to be one:
public sealed class Tree<T> : IReadOnlyCollection<Tree<T>> { private readonly IReadOnlyCollection<Tree<T>> children; public T Item { get; } public Tree(T item, IReadOnlyCollection<Tree<T>> children) { if (item == null) throw new ArgumentNullException(nameof(item)); if (children == null) throw new ArgumentNullException(nameof(children)); Item = item; this.children = children; } public Tree<TResult> Select<TResult>(Func<T, TResult> selector) { var mappedItem = selector(Item); var mappedChildren = new List<Tree<TResult>>(); foreach (var t in children) mappedChildren.Add(t.Select(selector)); return new Tree<TResult>(mappedItem, mappedChildren); } public int Count { get { return children.Count; } } public IEnumerator<Tree<T>> GetEnumerator() { return children.GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() { return children.GetEnumerator(); } public override bool Equals(object obj) { if (!(obj is Tree<T> other)) return false; return Equals(Item, other.Item) && Enumerable.SequenceEqual(this, other); } public override int GetHashCode() { return Item.GetHashCode() ^ children.GetHashCode(); } }
As is usually the case, you can implement a tree in more than one way. Here, I chose an approach where Tree<T> contains an Item and is a collection of (sub)trees. Notice that the definition is recursive: in addition to its Item, each Tree<T> object also contains a finite collection of other trees. You create leaf nodes with empty collections.
This variation uses finite collections (IReadOnlyCollection<T>), but you could also enable infinite trees by instead using potentially infinite sequences (IEnumerable<T>). This would slightly complicate the implementation of the Select method, though, so I decided to leave that as an exercise to the reader.
The Select method first translates the contained Item using the selector function, and then recursively calls itself for each sub-tree in children. This method has the desired signature, and furthermore obeys the functor laws, as you'll see later in the article. Tree<T> is a functor.
Usage #
While you can create trees directly with the Tree<T> constructor, a few static helper methods makes it smoother:
public static class Tree { public static Tree<T> Leaf<T>(T item) { return new Tree<T>(item, new Tree<T>[0]); } public static Tree<T> Create<T>(T item, params Tree<T>[] children) { return new Tree<T>(item, children); } }
This enables you to create a tree like this:
var source = Tree.Create(42, Tree.Create(1337, Tree.Leaf(-3)), Tree.Create(7, Tree.Leaf(-99), Tree.Leaf(100), Tree.Leaf(0)));
This is a tree containing integers. You can translate it to a tree containing strings like this:
Tree<string> dest = source.Select(i => i.ToString());
or like this:
Tree<string> dest = from i in source select i.ToString();
In both of these examples, I've explicitly declared the type of dest instead of using the var keyword. There's no practical reason to do this; I only did it to make the type clear to you.
Haskell #
Haskell has a more explicit model of functors, and the language features to support it. The Haskell equivalent to the above Tree<T> class is literally one line of code:
data Tree a = Tree a [Tree a] deriving (Show, Eq, Functor)
Notice that the Haskell compiler can automatically derive an implementation of the Functor typeclass, although that does require the DeriveFunctor language extension.
You can expend a few more lines of code for utility functions, so that it looks like you're actually programming:
leaf :: a -> Tree a leaf x = Tree x [] create :: a -> [Tree a] -> Tree a create = Tree
These functions correspond to the static methods on the above Tree class. With them, you can now create a tree:
source :: Tree Int source = create 42 [ create 1337 [ leaf (-3)], create 7 [ leaf (-99), leaf 100, leaf 0]]
You can translate such a tree of integers to a tree of strings with the fmap function:
dest :: Tree String dest = fmap show source
or with the infix operator:
dest :: Tree String dest = show <$> source
The <$> operator is an alias for fmap.
F# #
In F#, the type definition has the same structure as in Haskell:
type Tree<'a> = Tree of ('a * Tree<'a> list)
Unlike Haskell, however, F# doesn't have any built-in functor awareness, so you'll have to implement the map function yourself:
// ('a -> 'b) -> Tree<'a> -> Tree<'b> let rec map f (Tree (x, children)) = let mappedX = f x let mappedChildren = children |> List.map (map f) Tree (mappedX, mappedChildren)
Notice that you have to use the rec keyword in order to make map recursive. The implementation is similar to the C# code: first use f to map the contained item, and then recursively map the children.
To keep all three examples equivalent, you can also define utility functions:
// 'a -> Tree<'a> let leaf x = Tree (x, List.empty) // 'a -> Tree<'a> list -> Tree<'a> let create x children = Tree (x, children)
This enables you to create a tree like this:
// Tree<int> let source = Tree.create 42 [ Tree.create 1337 [ Tree.leaf -3] Tree.create 7 [ Tree.leaf -99 Tree.leaf 100 Tree.leaf 0]]
which you can translate like this:
// Tree<string> let dest = source |> Tree.map string
Here, all of the above functions are defined in a module named Tree.
First functor law #
The Select method obeys the first functor law. As usual, it's proper computer-science work to actually prove that, but you can write some tests to demonstrate the first functor law for the Tree<T> class. In this article, you'll see a few parametrised tests written with xUnit.net. First, you can define some reusable trees as test input:
public static IEnumerable<object[]> Trees { get { yield return new[] { Tree.Leaf(42) }; yield return new[] { Tree.Create(-32, Tree.Leaf(0)) }; yield return new[] { Tree.Create(99, Tree.Leaf(90), Tree.Leaf(2)) }; yield return new[] { Tree.Create(99, Tree.Leaf(90), Tree.Create(2, Tree.Leaf(-3))) }; yield return new[] { Tree.Create(42, Tree.Create(1337, Tree.Leaf(-3)), Tree.Create(7, Tree.Leaf(-99), Tree.Leaf(100), Tree.Leaf(0))) }; } }
This is just a collection of five small trees that can be used as input for parametrised tests. The first tree is only a single node - the simplest tree you can make with the Tree<T> class.
You can use this static property as a source of input for parametrised tests. Here's one that demonstrates that the first functor law holds:
[Theory, MemberData(nameof(Trees))] public void FirstFunctorLaw(Tree<int> tree) { Assert.Equal(tree, tree.Select(x => x)); }
Here, I chose to implement the identity function as an anonymous lambda expression. In contrast, in the previous article, I explicitly declared a function variable and called it id. Those two ways to express the identity function are equivalent.
As always, I'd like to emphasise that this test doesn't prove that Tree<T> obeys the first functor law. It only demonstrates that the law holds for those five examples.
Second functor law #
Like the above example, you can also write a parametrised test that demonstrates that Tree<T> obeys the second functor law. You can reuse the Trees test case source for that test:
[Theory, MemberData(nameof(Trees))] public void SecondFunctorLaw(Tree<int> tree) { string g(int i) => i.ToString(); bool f(string s) => s.Length % 2 == 0; Assert.Equal(tree.Select(g).Select(f), tree.Select(i => f(g(i)))); }
This test defines two local functions, f and g. Instead of explicitly declaring the functions as Func variables, this test uses a (relatively) new C# feature called local functions.
Again, while the test doesn't prove anything, it demonstrates that for the five test cases, it doesn't matter if you project the tree in one or two steps.
Summary #
This was the second example of a functor implemented in a statically typed object-oriented language, but contrasted with implementations in statically typed functional languages. The concept of a functor translates without much loss of fidelity, but you'll have to write more verbose code. A language like C# isn't optimised for functors or their like; Haskell and F# are.
The purpose of this article series is to show enough examples of functors that you should start to see a pattern. Keep in mind, though, that a functor isn't a design pattern. It's a mathematical concept.
Next: A rose tree functor.
