# 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.