Church-encoded rose tree by Mark Seemann

A rose tree is a tree with leaf nodes of one type, and internal nodes of another.

This article is part of a series of articles about Church encoding. In the previous articles, you've seen how to implement a Maybe container, and how to implement an Either container. Through these examples, you've learned how to model sum types without explicit language support. In this article, you'll see how to model a rose tree.

A rose tree is a general-purpose data structure where each node in a tree has an associated value. Each node can have an arbitrary number of branches, including none. The distinguishing feature from a rose tree and just any tree is that internal nodes can hold values of a different type than leaf values.

The diagram shows an example of a tree of internal integers and leaf strings. All internal nodes contain integer values, and all leaves contain strings. Each node can have an arbitrary number of branches.

Contract #

In C#, you can represent the fundamental structure of a rose tree with a Church encoding, starting with an interface:

public interface IRoseTree<N, L>
{
    TResult Match<TResult>(
        Func<N, IEnumerable<IRoseTree<N, L>>, TResult> node,
        Func<L, TResult> leaf);
}

The structure of a rose tree includes two mutually exclusive cases: internal nodes and leaf nodes. Since there's two cases, the Match method takes two arguments, one for each case.

The interface is generic, with two type arguments: N (for Node) and L (for leaf). Any consumer of an IRoseTree<N, L> object must supply two functions when calling the Match method: a function that turns a node into a TResult value, and a function that turns a leaf into a TResult value.

Both cases must have a corresponding implementation.

Leaves #

The leaf implementation is the simplest:

public sealed class RoseLeaf<N, L> : IRoseTree<N, L>
{
    private readonly L value;
 
    public RoseLeaf(L value)
    {
        this.value = value;
    }
 
    public TResult Match<TResult>(
        Func<N, IEnumerable<IRoseTree<N, L>>, TResult> node,
        Func<L, TResult> leaf)
    {
        return leaf(value);
    }
 
    public override bool Equals(object obj)
    {
        if (!(obj is RoseLeaf<N, L> other))
            return false;
 
        return Equals(value, other.value);
    }
 
    public override int GetHashCode()
    {
        return value.GetHashCode();
    }
}

The RoseLeaf class is an Adapter over a value of the generic type L. As is always the case with Church encoding, it implements the Match method by unconditionally calling one of the arguments, in this case the leaf function, with its adapted value.

While it doesn't have to do this, it also overrides Equals and GetHashCode. This is an immutable class, so it's a great candidate to be a Value Object. Making it a Value Object makes it easier to compare expected and actual values in unit tests, among other benefits.

Nodes #

The node implementation is slightly more complex:

public sealed class RoseNode<N, L> : IRoseTree<N, L>
{
    private readonly N value;
    private readonly IEnumerable<IRoseTree<N, L>> branches;
 
    public RoseNode(N value, IEnumerable<IRoseTree<N, L>> branches)
    {
        this.value = value;
        this.branches = branches;
    }
 
    public TResult Match<TResult>(
        Func<N, IEnumerable<IRoseTree<N, L>>, TResult> node,
        Func<L, TResult> leaf)
    {
        return node(value, branches);
    }
 
    public override bool Equals(object obj)
    {
        if (!(obj is RoseNode<N, L> other))
            return false;
 
        return Equals(value, other.value)
            && Enumerable.SequenceEqual(branches, other.branches);
    }
 
    public override int GetHashCode()
    {
        return value.GetHashCode() ^ branches.GetHashCode();
    }
}

A node contains both a value (of the type N) and a collection of sub-trees, or branches. The class implements the Match method by unconditionally calling the node function argument with its constituent values.

Again, it overrides Equals and GetHashCode for the same reasons as RoseLeaf. This isn't required to implement Church encoding, but makes comparison and unit testing easier.

Usage #

You can use the RoseLeaf and RoseNode constructors to create new trees, but it sometimes helps to have a static helper method to create values. It turns out that there's little value in a helper method for leaves, but for nodes, it's marginally useful:

public static IRoseTree<N, L> Node<N, L>(N value, params IRoseTree<N, L>[] branches)
{
    return new RoseNode<N, L>(value, branches);
}

This enables you to create tree objects, like this:

IRoseTree<string, int> tree =
    RoseTree.Node("foo", new RoseLeaf<string, int>(42), new RoseLeaf<string, int>(1337));

That's a single node with the label "foo" and two leaves with the values 42 and 1337, respectively. You can create the tree shown in the above diagram like this:

IRoseTree<int, string> exampleTree =
    RoseTree.Node(42,
        RoseTree.Node(1337,
            new RoseLeaf<int, string>("foo"),
            new RoseLeaf<int, string>("bar")),
        RoseTree.Node(2112,
            RoseTree.Node(90125,
                new RoseLeaf<int, string>("baz"),
                new RoseLeaf<int, string>("qux"),
                new RoseLeaf<int, string>("quux")),
            new RoseLeaf<int, string>("quuz")),
        new RoseLeaf<int, string>("corge"));

You can add various extension methods to implement useful functionality. In later articles, you'll see some more compelling examples, so here, I'm only going to show a few basic examples. One of the simplest features you can add is a method that will tell you if an IRoseTree<N, L> object is a node or a leaf:

public static IChurchBoolean IsLeaf<N, L>(this IRoseTree<N, L> source)
{
    return source.Match<IChurchBoolean>(
        node: (_, __) => new ChurchFalse(),
        leaf: _ => new ChurchTrue());
}
 
public static IChurchBoolean IsNode<N, L>(this IRoseTree<N, L> source)
{
    return new ChurchNot(source.IsLeaf());
}

Since this article is part of the overall article series on Church encoding, and the purpose of that article series is also to show how basic language features can be created from Church encodings, these two methods return Church-encoded Boolean values instead of the built-in bool type. I'm sure you can imagine how you could change the type to bool if you'd like.

You can use these methods like this:

> IRoseTree<Guid, double> tree = new RoseLeaf<Guid, double>(-3.2);
> tree.IsLeaf()
ChurchTrue { }
> tree.IsNode()
ChurchNot(ChurchTrue)
> IRoseTree<long, string> tree = RoseTree.Node<long, string>(42);
> tree.IsLeaf()
ChurchFalse { }
> tree.IsNode()
ChurchNot(ChurchFalse)

In a future article, you'll see some more compelling examples.

Terminology #

It's not entirely clear what to call a tree like the one shown here. The Wikipedia entry doesn't state one way or the other whether internal node types ought to be distinguishable from leaf node types, but there are indications that this could be the case. At least, it seems that the term isn't well-defined, so I took the liberty to retcon the name rose tree to the data structure shown here.

In the paper that introduces the rose tree term, Meertens writes:

"We consider trees whose internal nodes may fork into an arbitrary (natural) number of sub-trees. (If such a node has zero descendants, we still consider it internal.) Each external node carries a data item. No further information is stored in the tree; in particular, internal nodes are unlabelled."

public class Unit
{
    public readonly static Unit Instance = new Unit();
 
    private Unit() { }
}

This enables you to create a rose tree according to Meertens' definition:

IRoseTree<Unit, int> meertensTree =
    RoseTree.Node(Unit.Instance,
        RoseTree.Node(Unit.Instance,
            RoseTree.Node(Unit.Instance,
                new RoseLeaf<Unit, int>(2112)),
            new RoseLeaf<Unit, int>(42),
            new RoseLeaf<Unit, int>(1337),
            new RoseLeaf<Unit, int>(90125)),
        RoseTree.Node(Unit.Instance,
            new RoseLeaf<Unit, int>(1984)),
        new RoseLeaf<Unit, int>(666));

Visually, you could draw it like this:

Thus, the tree structure shown here seems to be a generalisation of Meertens' original definition.

I'm not a mathematician, so I may have misunderstood some things. If you have a better name than rose tree for the data structure shown here, please leave a comment.

Yeats #

Now that we're on the topic of rose tree as a term, you may, as a bonus, enjoy a similarly-titled poem:

THE ROSE TREE

"O words are lightly spoken"
Said Pearse to Connolly,
"Maybe a breath of politic words
Has withered our Rose Tree;
Or maybe but a wind that blows
Across the bitter sea."

"It needs to be but watered,"
James Connolly replied,
"To make the green come out again
And spread on every side,
And shake the blossom from the bud
To be the garden's pride."

"But where can we draw water"
Said Pearse to Connolly,
"When all the wells are parched away?
O plain as plain can be
There's nothing but our own red blood
Can make a right Rose Tree."

Summary #

You may occasionally find use for a tree that distinguishes between internal and leaf nodes. You can model such a tree with a Church encoding, as shown in this article.

Next: Catamorphisms.

Comments

type HeterogeneousRoseTree = Tree

type LeafLabeledRoseTree b = Tree () b

type BranchLabeledRoseTree a = Tree a ()

type HomogeneousRoseTree a = Tree a a

type UnlabelledRoseTree = Tree () ()

• ← Previous
• Archive
• Next →