A rose tree functor by Mark Seemann
Rose trees form normal functors. A place-holder article for object-oriented programmers.
This article is an instalment in an article series about functors. As another article explains, a rose tree is a bifunctor. This makes it trivially a functor. As such, this article is mostly a place-holder to fit the spot in the functor table of contents, thereby indicating that rose trees are functors.
Since a rose tree is a bifunctor, it's actually not one, but two, functors. Many languages, C# included, are best equipped to deal with unambiguous functors. This is also true in Haskell, where you'd usally define the Functor instance over a bifunctor's right, or second, side. Likewise, in C#, you can make IRoseTree<N, L> a functor by implementing Select:
public static IRoseTree<N, L1> Select<N, L, L1>( this IRoseTree<N, L> source, Func<L, L1> selector) { return source.SelectLeaf(selector); }
This method simply delegates all implementation to the SelectLeaf method; it's just SelectLeaf by another name. It obeys the functor laws, since these are just specializations of the bifunctor laws, and we know that a rose tree is a proper bifunctor.
It would have been technically possible to instead implement a Select method by calling SelectNode, but it seems marginally more useful to enable syntactic sugar for mapping over the leaves.
Menu example #
As an example, imagine that you're defining part of a menu bar for an old-fashioned desktop application. Perhaps you're even loading the structure of the menu from a text file. Doing so, you could create a simple tree that represents the edit menu:
IRoseTree<string, string> editMenuTemplate = RoseTree.Node("Edit", RoseTree.Node("Find and Replace", new RoseLeaf<string, string>("Find"), new RoseLeaf<string, string>("Replace")), RoseTree.Node("Case", new RoseLeaf<string, string>("Upper"), new RoseLeaf<string, string>("Lower")), new RoseLeaf<string, string>("Cut"), new RoseLeaf<string, string>("Copy"), new RoseLeaf<string, string>("Paste"));
At this point, you have an IRoseTree<string, string>, so you might as well have used a 'normal' tree instead of a rose tree. The above template, however, is only a first step, because you have this Command class:
public class Command { public Command(string name) { Name = name; } public string Name { get; } public virtual void Execute() { } }
Apart from this base class, you also have classes that derive from it: FindCommand, ReplaceCommand, and so on. These classes override the Execute method by implenting find, replace, etc. functionality. Imagine that you also have a store or dictionary of these derived objects. This enables you to transform the template tree into a useful user menu:
IRoseTree<string, Command> editMenu = from name in editMenuTemplate select commandStore.Lookup(name);
Notice how this transforms only the leaves, using the command store's Lookup method. This example uses C# query syntax, because this is what the Select method enables, but you could also have written the translation by just calling the Select method.
The internal nodes in a menu have no behavious, so it makes little sense to attempt to turn them into Command objects as well. They're only there to provide structure to the menu. With a 'normal' tree, you wouldn't have been able to enrich only the leaves, while leaving the internal nodes untouched, but with a rose tree you can.
The above example uses the Select method (via query syntax) to translate the nodes, thereby providing a demonstration of how to use the rose tree as the functor it is.
Summary #
The Select doesn't implement any behaviour not already provided by SelectLeaf, but it enables C# query syntax. The C# compiler understands functors, but not bifunctors, so when you have a bifunctor, you might as well light up that language feature as well by adding a Select method.
Next: A Visitor functor.
