Functor compositions by Mark Seemann
A functor nested within another functor forms a functor. With examples in C# and another language.
This article is part of a series of articles about functor relationships. In this one you'll learn about a universal composition of functors. In short, if you have one functor nested within another functor, then this composition itself gives rise to a functor.
Together with other articles in this series, this result can help you answer questions such as: Does this data structure form a functor?
Since functors tend to be quite common, and since they're useful enough that many programming languages have special support or syntax for them, the ability to recognize a potential functor can be useful. Given a type like Foo<T> (C# syntax) or Bar<T1, T2>, being able to recognize it as a functor can come in handy. One scenario is if you yourself have just defined this data type. Recognizing that it's a functor strongly suggests that you should give it a Select method in C#, a map function in F#, and so on.
Not all generic types give rise to a (covariant) functor. Some are rather contravariant functors, and some are invariant.
If, on the other hand, you have a data type where one functor is nested within another functor, then the data type itself gives rise to a functor. You'll see some examples in this article.
Abstract shape #
Before we look at some examples found in other code, it helps if we know what we're looking for. Imagine that you have two functors F and G, and you're now considering a data structure that contains a value where G is nested inside of F.
public sealed class GInF<T> { private readonly F<G<T>> ginf; public GInF(F<G<T>> ginf) { this.ginf = ginf; } // Methods go here...
The GInF<T> class has a single class field. The type of this field is an F container, but 'inside' F there's a G functor.
This kind of data structure gives rise to a functor. Knowing that, you can give it a Select method:
public GInF<TResult> Select<TResult>(Func<T, TResult> selector) { return new GInF<TResult>(ginf.Select(g => g.Select(selector))); }
The composed Select method calls Select on the F functor, passing it a lambda expression that calls Select on the G functor. That nested Select call produces an F<G<TResult>> that the composed Select method finally wraps in a new GInF<TResult> object that it returns.
I'll have more to say about how this generalizes to a nested composition of more than two functors, but first, let's consider some examples.
Priority list #
A common configuration is when the 'outer' functor is a collection, and the 'inner' functor is some other kind of container. The article An immutable priority collection shows a straightforward example. The PriorityCollection<T> class composes a single class field:
private readonly Prioritized<T>[] priorities;
The priorities field is an array (a collection) of Prioritized<T> objects. That type is a simple record type:
public sealed record Prioritized<T>(T Item, byte Priority);
If we squint a little and consider only the parameter list, we may realize that this is fundamentally an 'embellished' tuple: (T Item, byte Priority). A pair forms a bifunctor, but in the Haskell Prelude a tuple is also a Functor instance over its rightmost element. In other words, if we'd swapped the Prioritized<T> constructor parameters, it might have naturally looked like something we could fmap:
ghci> fmap (elem 'r') (55, "foo") (55,False)
Here we have a tuple of an integer and a string. Imagine that the number 55 is the priority that we give to the label "foo". This little ad-hoc example demonstrates how to map that tuple to another tuple with a priority, but now it instead holds a Boolean value indicating whether or not the string contained the character 'r' (which it didn't).
You can easily swap the elements:
ghci> import Data.Tuple
ghci> swap (55, "foo")
("foo",55)
This looks just like the Prioritized<T> parameter list. This also implies that if you originally have the parameter list in that order, you could swap it, map it, and swap it again:
ghci> swap $ fmap (elem 'r') $ swap ("foo", 55)
(False,55)
My point is only that Prioritized<T> is isomorphic to a known functor. In reality you rarely need to analyze things that thoroughly to come to that realization, but the bottom line is that you can give Prioritized<T> a lawful Select method:
public sealed record Prioritized<T>(T Item, byte Priority) { public Prioritized<TResult> Select<TResult>(Func<T, TResult> selector) { return new(selector(Item), Priority); } }
Hardly surprising, but since this article postulates that a functor of a functor is a functor, and since we already know that collections give rise to a functor, we should deduce that we can give PriorityCollection<T> a Select method. And we can:
public PriorityCollection<TResult> Select<TResult>(Func<T, TResult> selector) { return new PriorityCollection<TResult>( priorities.Select(p => p.Select(selector)).ToArray()); }
Notice how much this implementation looks like the above GInF<T> 'shape' implementation.
Tree #
An example only marginally more complicated than the above is shown in A Tree functor. The Tree<T> class shown in that article contains two constituents:
private readonly IReadOnlyCollection<Tree<T>> children; public T Item { get; }
Just like PriorityCollection<T> there's a collection, as well as a 'naked' T value. The main difference is that here, the collection is of the same type as the object itself: Tree<T>.
You've seen a similar example in the previous article, which also had a recursive data structure. If you assume, however, that Tree<T> gives rise to a functor, then so does the nested composition of putting it in a collection. This means, from the 'theorem' put forth in this article, that IReadOnlyCollection<Tree<T>> composes as a functor. Finally you have a product of a T (which is isomorphic to the Identity functor) and that composed functor. From Functor products it follows that that's a functor too, which explains why Tree<T> forms a functor. The article shows the Select implementation.
Binary tree Zipper #
In both previous articles you've seen pieces of the puzzle explaining why the binary tree Zipper gives rise to functor. There's one missing piece, however, that we can now finally address.
Recall that BinaryTreeZipper<T> composes these two objects:
public BinaryTree<T> Tree { get; } public IEnumerable<Crumb<T>> Breadcrumbs { get; }
We've already established that both BinaryTree<T> and Crumb<T> form functors. In this article you've learned that a functor in a functor is a functor, which applies to IEnumerable<Crumb<T>>. Both of the above read-only properties are functors, then, which means that the entire class is a product of functors. The Select method follows:
public BinaryTreeZipper<TResult> Select<TResult>(Func<T, TResult> selector) { return new BinaryTreeZipper<TResult>( Tree.Select(selector), Breadcrumbs.Select(c => c.Select(selector))); }
Notice that this Select implementation calls Select on the 'outer' Breadcrumbs by calling Select on each Crumb<T>. This is similar to the previous examples in this article.
Other nested containers #
There are plenty of other examples of functors that contains other functor values. Asynchronous programming supplies its own family of examples.
The way that C# and many other languages model asynchronous or I/O-bound actions is to wrap them in a Task container. If the value inside the Task<T> container is itself a functor, you can make that a functor, too. Examples include Task<IEnumerable<T>>, Task<Maybe<T>> (or its close cousin Task<T?>; notice the question mark), Task<Result<T1, T2>>, etc. You'll run into such types every time you have an I/O-bound or concurrent operation that returns IEnumerable<T>, Maybe<T> etc. as an asynchronous result.
While you can make such nested task functors a functor in its own right, you rarely need that in languages with native async and await features, since those languages nudge you in other directions.
You can, however, run into other issues with task-based programming, but you'll see examples and solutions in a future article.
You'll run into other examples of nested containers with many property-based testing libraries. They typically define Test Data Generators, often called Gen<T>. For .NET, both FsCheck, Hedgehog, and CsCheck does this. For Haskell, QuickCheck, too, defines Gen a.
You often need to generate random collections, in which case you'd work with Gen<IEnumerable<T>> or a similar collection type. If you need random Maybe values, you'll work with Gen<Maybe<T>>, and so on.
On the other hand, sometimes you need to work with a collection of generators, such as seq<Gen<'a>>.
These are all examples of functors within functors. It's not a given that you must treat such a combination as a functor in its own right. To be honest, typically, you don't. On the other hand, if you find yourself writing Select within Select, or map within map, depending on your language, it might make your code more succinct and readable if you give that combination a specialized functor affordance.
Higher arities #
Like the previous two articles, the 'theorem' presented here generalizes to more than two functors. If you have a third H functor, then F<G<H<T>>> also gives rise to a functor. You can easily prove this by simple induction. We may first consider the base case. With a single functor (n = 1) any functor (say, F) is trivially a functor.
In the induction step (n > 1), you then assume that the n - 1 'stack' of functors already gives rise to a functor, and then proceed to prove that the configuration where all those nested functors are wrapped by yet another functor also forms a functor. Since the 'inner stack' of functors forms a functor (by assumption), you only need to prove that a configuration of the outer functor, and that 'inner stack', gives rise to a functor. You've seen how this works in this article, but I admit that a few examples constitute no proof. I'll leave you with only a sketch of this step, but you may consider using equational reasoning as demonstrated by Bartosz Milewski and then prove the functor laws for such a composition.
The Haskell Data.Functor.Compose module defines a general-purpose data type to compose functors. You may, for example, compose a tuple inside a Maybe inside a list:
thriceNested :: Compose [] (Compose Maybe ((,) Integer)) String thriceNested = Compose [Compose (Just (42, "foo")), Compose Nothing, Compose (Just (89, "ba"))]
You can easily fmap that data structure, for example by evaluating whether the number of characters in each string is an odd number (if it's there at all):
ghci> fmap (odd . length) thriceNested Compose [Compose (Just (42,True)),Compose Nothing,Compose (Just (89,False))]
The first element now has True as the second tuple element, since "foo" has an odd number of characters (3). The next element is Nothing, because Nothing maps to Nothing. The third element has False in the rightmost tuple element, since "ba" doesn't have an odd number of characters (it has 2).
Relations to monads #
A nested 'stack' of functors may remind you of the way that I prefer to teach monads: A monad is a functor your can flatten. In short, the definition is the ability to 'flatten' F<F<T>> to F<T>. A function that can do that is often called join or Flatten.
So far in this article, we've been looking at stacks of different functors, abstractly denoted F<G<T>>. There's no rule, however, that says that F and G may not be the same. If F = G then F<G<T>> is really F<F<T>>. This starts to look like the antecedent of the monad definition.
While the starting point may be the same, these notions are not equivalent. Yes, F<F<T>> may form a monad (if you can flatten it), but it does, universally, give rise to a functor. On the other hand, we can hardly talk about flattening F<G<T>>, because that would imply that you'd have to somehow 'throw away' either F or G. There may be specific functors (e.g. Identity) for which this is possible, but there's no universal law to that effect.
Not all 'stacks' of functors are monads. All monads, on the other hand, are functors.
Conclusion #
A data structure that configures one type of functor inside of another functor itself forms a functor. The examples shown in this article are mostly constrained to two functors, but if you have a 'stack' of three, four, or more functors, that arrangement still gives rise to a functor.
This is useful to know, particularly if you're working in a language with only partial support for functors. Mainstream languages aren't going to automatically turn such stacks into functors, in the way that Haskell's Compose container almost does. Thus, knowing when you can safely give your generic types a Select method or map function may come in handy.
To be honest, though, this result is hardly the most important 'theorem' concerning stacks of functors. In reality, you often run into situations where you do have a stack of functors, but they're in the wrong order. You may have a collection of asynchronous tasks, but you really need an asynchronous task that contains a collection of values. The next article addresses that problem.
Next: Traversals.
