Rose tree bifunctor by Mark Seemann
A rose tree forms a bifunctor. An article for object-oriented developers.
This article is an instalment in an article series about bifunctors. While the overview article explains that there's essentially two practically useful bifunctors, here's a third one. rose trees.
Mapping both dimensions #
Like in the previous article on the Either bifunctor, I'll start by implementing the simultaneous two-dimensional translation SelectBoth:
public static IRoseTree<N1, L1> SelectBoth<N, N1, L, L1>( this IRoseTree<N, L> source, Func<N, N1> selectNode, Func<L, L1> selectLeaf) { return source.Cata( node: (n, branches) => new RoseNode<N1, L1>(selectNode(n), branches), leaf: l => (IRoseTree<N1, L1>)new RoseLeaf<N1, L1>(selectLeaf(l))); }
This article uses the previously shown Church-encoded rose tree and its catamorphism Cata.
In the leaf case, the l argument received by the lambda expression is an object of the type L, since the source tree is an IRoseTree<N, L> object; i.e. a tree with leaves of the type L and nodes of the type N. The selectLeaf argument is a function that converts an L object to an L1 object. Since l is an L object, you can call selectLeaf with it to produce an L1 object. You can use this resulting object to create a new RoseLeaf<N1, L1>. Keep in mind that while the RoseLeaf class requires two type arguments, it never requires an object of its N type argument, which means that you can create an object with any node type argument, including N1, even if you don't have an object of that type.
In the node case, the lambda expression receives two objects: n and branches. The n object has the type N, while the branches object has the type IEnumerable<IRoseTree<N1, L1>>. In other words, the branches have already been translated to the desired result type. That's how the catamorphism works. This means that you only have to figure out how to translate the N object n to an N1 object. The selectNode function argument can do that, so you can then create a new RoseNode<N1, L1> and return it.
This works as expected:
> var tree = RoseTree.Node("foo", new RoseLeaf<string, int>(42), new RoseLeaf<string, int>(1337)); > tree RoseNode<string, int>("foo", IRoseTree<string, int>[2] { 42, 1337 }) > tree.SelectBoth(s => s.Length, i => i.ToString()) RoseNode<int, string>(3, IRoseTree<int, string>[2] { "42", "1337" })
This C# Interactive example shows how to convert a tree with internal string nodes and integer leaves to a tree of internal integer nodes and string leaves. The strings are converted to strings by counting their Length, while the integers are turned into strings using the standard ToString method available on all objects.
Mapping nodes #
When you have SelectBoth, you can trivially implement the translations for each dimension in isolation. For tuple bifunctors, I called these methods SelectFirst and SelectSecond, while for Either bifunctors, I chose to name them SelectLeft and SelectRight. Continuing the trend of naming the translations after what they translate, instead of their positions, I'll name the corresponding methods here SelectNode and SelectLeaf. In Haskell, the functions associated with Data.Bifunctor are always called first and second, but I see no reason to preserve such abstract naming in C#. In Haskell, these functions are part of the Bifunctor type class; the abstract names serve an actual purpose. This isn't the case in C#, so there's no reason to retain the abstract names. You might as well use names that communicate intent, which is what I've tried to do here.
If you want to map only the internal nodes, you can implement a SelectNode method based on SelectBoth:
public static IRoseTree<N1, L> SelectNode<N, N1, L>( this IRoseTree<N, L> source, Func<N, N1> selector) { return source.SelectBoth(selector, l => l); }
This simply uses the l => l lambda expression as an ad-hoc identity function, while passing selector as the selectNode argument to the SelectBoth method.
You can use this to map the above tree to a tree made entirely of numbers:
> var tree = RoseTree.Node("foo", new RoseLeaf<string, int>(42), new RoseLeaf<string, int>(1337)); > tree.SelectNode(s => s.Length) RoseNode<int, int>(3, IRoseTree<int, int>[2] { 42, 1337 })
Such a tree is, incidentally, isomorphic to a 'normal' tree. It might be a good exercise, if you need one, to demonstrate the isormorphism by writing functions that convert a Tree<T> into an IRoseTree<T, T>, and vice versa.
Mapping leaves #
Similar to SelectNode, you can also trivially implement SelectLeaf:
public static IRoseTree<N, L1> SelectLeaf<N, L, L1>( this IRoseTree<N, L> source, Func<L, L1> selector) { return source.SelectBoth(n => n, selector); }
This is another one-liner calling SelectBoth, with the difference that the identity function n => n is passed as the first argument, instead of as the last. This ensures that only RoseLeaf values are mapped:
> var tree = RoseTree.Node("foo", new RoseLeaf<string, int>(42), new RoseLeaf<string, int>(1337)); > tree.SelectLeaf(i => i % 2 == 0) RoseNode<string, bool>("foo", IRoseTree<string, bool>[2] { true, false })
In the above C# Interactive session, the leaves are mapped to Boolean values, indicating whether they're even or odd.
Identity laws #
Rose trees obey all the bifunctor laws. While it's formal work to prove that this is the case, you can get an intuition for it via examples. Often, I use a property-based testing library like FsCheck or Hedgehog to demonstrate (not prove) that laws hold, but in this article, I'll keep it simple and only cover each law with a parametrised test.
private static T Id<T>(T x) => x; public static IEnumerable<object[]> BifunctorLawsData { get { yield return new[] { new RoseLeaf<int, string>("") }; yield return new[] { new RoseLeaf<int, string>("foo") }; yield return new[] { RoseTree.Node<int, string>(42) }; yield return new[] { RoseTree.Node(42, new RoseLeaf<int, string>("bar")) }; yield return new[] { exampleTree }; } } [Theory, MemberData(nameof(BifunctorLawsData))] public void SelectNodeObeysFirstFunctorLaw(IRoseTree<int, string> t) { Assert.Equal(t, t.SelectNode(Id)); }
This test uses xUnit.net's [Theory] feature to supply a small set of example input values. The input values are defined by the BifunctorLawsData property, since I'll reuse the same values for all the bifunctor law demonstration tests. The exampleTree object is the tree shown in Church-encoded rose tree.
The tests also use the identity function implemented as a private function called Id, since C# doesn't come equipped with such a function in the Base Class Library.
For all the IRoseTree<int, string> objects t, the test simply verifies that the original tree t is equal to the tree projected over the first axis with the Id function.
Likewise, the first functor law applies when translating over the second dimension:
[Theory, MemberData(nameof(BifunctorLawsData))] public void SelectLeafObeysFirstFunctorLaw(IRoseTree<int, string> t) { Assert.Equal(t, t.SelectLeaf(Id)); }
This is the same test as the previous test, with the only exception that it calls SelectLeaf instead of SelectNode.
Both SelectNode and SelectLeaf are implemented by SelectBoth, so the real test is whether this method obeys the identity law:
[Theory, MemberData(nameof(BifunctorLawsData))] public void SelectBothObeysIdentityLaw(IRoseTree<int, string> t) { Assert.Equal(t, t.SelectBoth(Id, Id)); }
Projecting over both dimensions with the identity function does, indeed, return an object equal to the input object.
Consistency law #
In general, it shouldn't matter whether you map with SelectBoth or a combination of SelectNode and SelectLeaf:
[Theory, MemberData(nameof(BifunctorLawsData))] public void ConsistencyLawHolds(IRoseTree<int, string> t) { DateTime f(int i) => new DateTime(i); bool g(string s) => string.IsNullOrWhiteSpace(s); Assert.Equal(t.SelectBoth(f, g), t.SelectLeaf(g).SelectNode(f)); Assert.Equal( t.SelectNode(f).SelectLeaf(g), t.SelectLeaf(g).SelectNode(f)); }
This example creates two local functions f and g. The first function, f, creates a new DateTime object from an integer, using one of the DateTime constructor overloads. The second function, g, just delegates to string.IsNullOrWhiteSpace, although I want to stress that this is just an example. The law should hold for any two (pure) functions.
The test then verifies that you get the same result from calling SelectBoth as when you call SelectNode followed by SelectLeaf, or the other way around.
Composition laws #
The composition laws insist that you can compose functions, or translations, and that again, the choice to do one or the other doesn't matter. Along each of the axes, it's just the second functor law applied. This parametrised test demonstrates that the law holds for SelectNode:
[Theory, MemberData(nameof(BifunctorLawsData))] public void SecondFunctorLawHoldsForSelectNode(IRoseTree<int, string> t) { char f(bool b) => b ? 'T' : 'F'; bool g(int i) => i % 2 == 0; Assert.Equal( t.SelectNode(x => f(g(x))), t.SelectNode(g).SelectNode(f)); }
Here, f is a local function that returns the the character 'T' for true, and 'F' for false; g is the even function. The second functor law states that mapping f(g(x)) in a single step is equivalent to first mapping over g and then map the result of that using f.
The same law applies if you fix the first dimension and translate over the second:
[Theory, MemberData(nameof(BifunctorLawsData))] public void SecondFunctorLawHoldsForSelectLeaf(IRoseTree<int, string> t) { bool f(int x) => x % 2 == 0; int g(string s) => s.Length; Assert.Equal( t.SelectLeaf(x => f(g(x))), t.SelectLeaf(g).SelectLeaf(f)); }
Here, f is the even function, whereas g is a local function that returns the length of a string. Again, the test demonstrates that the output is the same whether you map over an intermediary step, or whether you map using only a single step.
This generalises to the composition law for SelectBoth:
[Theory, MemberData(nameof(BifunctorLawsData))] public void SelectBothCompositionLawHolds(IRoseTree<int, string> t) { char f(bool b) => b ? 'T' : 'F'; bool g(int x) => x % 2 == 0; bool h(int x) => x % 2 == 0; int i(string s) => s.Length; Assert.Equal( t.SelectBoth(x => f(g(x)), y => h(i(y))), t.SelectBoth(g, i).SelectBoth(f, h)); }
Again, whether you translate in one or two steps shouldn't affect the outcome.
As all of these tests demonstrate, the bifunctor laws hold for rose trees. The tests only showcase five examples, but I hope it gives you an intuition how any rose tree is a bifunctor. After all, the SelectNode, SelectLeaf, and SelectBoth methods are all generic, and they behave the same for all generic type arguments.
Summary #
Rose trees are bifunctors. You can translate the node and leaf dimension of a rose tree independently of each other, and the bifunctor laws hold for any pure translation, no matter how you compose the projections.
As always, there can be performance differences between the various compositions, but the outputs will be the same regardless of composition.
A functor, and by extension, a bifunctor, is a structure-preserving map. This means that any projection preserves the structure of the underlying container. For rose trees this means that the shape of the tree remains the same. The number of leaves remain the same, as does the number of internal nodes.
Next: Contravariant functors.
