# Functor products by Mark Seemann

*A tuple or class of functors is also a functor. An article for object-oriented developers.*

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 a product type of functors, that data structure 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 such a 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 which is a product of two or more (covariant) functors *with the same type parameter*, 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. Most (if not all?) languages support product types. In canonical form, they're just tuples of values, but in an object-oriented language like C#, such types are typically classes.

Imagine that you have two functors `F`

and `G`

, and you're now considering a data structure that contains a value of both types.

public sealed class FAndG<T> { public FAndG(F<T> f, G<T> g) { F = f; G = g; } public F<T> F { get; } public G<T> G { get; } // Methods go here...

The name of the type is `FAndG<T>`

because it contains both an `F<T>`

object and a `G<T>`

object.

Notice that it's an essential requirement that the individual functors (here `F`

and `G`

) are parametrized by the same type parameter (here `T`

). If your data structure contains `F<T1>`

and `G<T2>`

, the following 'theorem' doesn't apply.

The point of this article is that such an `FAndG<T>`

data structure forms a functor. The `Select`

implementation is quite unsurprising:

public FAndG<TResult> Select<TResult>(Func<T, TResult> selector) { return new FAndG<TResult>(F.Select(selector), G.Select(selector)); }

Since we've assumed that both `F`

and `G`

already are functors, they must come with some projection function. In C# it's idiomatically called `Select`

, while in F# it'd typically be called `map`

:

// ('a -> 'b) -> FAndG<'a> -> FAndG<'b> let map f fandg = { F = F.map f fandg.F; G = G.map f fandg.G }

assuming a record type like

type FAndG<'a> = { F : F<'a>; G : G<'a> }

In both the C# `Select`

example and the F# `map`

function, the composed functor passes the function argument (`selector`

or `f`

) to both `F`

and `G`

and uses it to map both constituents. It then composes a new product from these individual results.

I'll have more to say about how this generalizes to a product of more than two functors, but first, let's consider some examples.

### List Zipper #

One of the simplest example I can think of is a List Zipper, which in Haskell is nothing but a type alias of a tuple of lists:

`type ListZipper a = ([a],[a])`

In the article A List Zipper in C# you saw how the `ListZipper<T>`

class composes two `IEnumerable<T>`

objects.

private readonly IEnumerable<T> values; public IEnumerable<T> Breadcrumbs { get; } private ListZipper(IEnumerable<T> values, IEnumerable<T> breadcrumbs) { this.values = values; Breadcrumbs = breadcrumbs; }

Since we already know that sequences like `IEnumerable<T>`

form functors, we now know that so must `ListZipper<T>`

. And indeed, the `Select`

implementation looks similar to the above 'shape outline'.

public ListZipper<TResult> Select<TResult>(Func<T, TResult> selector) { return new ListZipper<TResult>(values.Select(selector), Breadcrumbs.Select(selector)); }

It passes the `selector`

function to the `Select`

method of both `values`

and `Breadcrumbs`

, and composes the results into a `new ListZipper<TResult>`

.

While this example is straightforward, it may not be the most compelling, because `ListZipper<T>`

composes two identical functors: `IEnumerable<T>`

. The knowledge that functors compose is more general than that.

### Non-empty collection #

Next after the above List Zipper, the simplest example I can think of is a non-empty list. On this blog I originally introduced it in the article Semigroups accumulate, but here I'll use the variant from NonEmpty catamorphism. It composes a single value of the type `T`

with an `IReadOnlyCollection<T>`

.

public NonEmptyCollection(T head, params T[] tail) { if (head == null) throw new ArgumentNullException(nameof(head)); this.Head = head; this.Tail = tail; } public T Head { get; } public IReadOnlyCollection<T> Tail { get; }

The `Tail`

, being an `IReadOnlyCollection<T>`

, easily forms a functor, since it's a kind of list. But what about `Head`

, which is a 'naked' `T`

value? Does that form a functor? If so, which one?

Indeed, a 'naked' `T`

value is isomorphic to the Identity functor. This situation is an example of how knowing about the Identity functor is useful, even if you never actually write code that uses it. Once you realize that `T`

is equivalent with a functor, you've now established that `NonEmptyCollection<T>`

composes two functors. Therefore, it must itself form a functor, and you realize that you can give it a `Select`

method.

public NonEmptyCollection<TResult> Select<TResult>(Func<T, TResult> selector) { return new NonEmptyCollection<TResult>(selector(Head), Tail.Select(selector).ToArray()); }

Notice that even though we understand that `T`

is equivalent to the Identity functor, there's no reason to actually wrap `Head`

in an `Identity<T>`

container just to call `Select`

on it and unwrap the result. Rather, the above `Select`

implementation directly invokes `selector`

with `Head`

. It is, after all, a function that takes a `T`

value as input and returns a `TResult`

object as output.

### Ranges #

It's hard to come up with an example that's both somewhat compelling and realistic, and at the same time prototypically pure. Stripped of all 'noise' functor products are just tuples, but that hardly makes for a compelling example. On the other hand, most other examples I can think of combine results about functors where they compose in more than one way. Not only as products, but also as sums of functors, as well as nested compositions. You'll be able to read about these in future articles, but for the next examples, you'll have to accept some claims about functors at face value.

In Range as a functor you saw how both `Endpoint<T>`

and `Range<T>`

are functors. The article shows functor implementations for each, in both C#, F#, and Haskell. For now we'll ignore the deeper underlying reason why `Endpoint<T>`

forms a functor, and instead focus on `Range<T>`

.

In Haskell I never defined an explicit `Range`

type, but rather just treated ranges as tuples. As stated repeatedly already, tuples are the essential products, so if you accept that `Endpoint`

gives rise to a functor, then a 'range tuple' does, too.

In F# `Range`

is defined like this:

`type Range<'a> = { LowerBound : Endpoint<'a>; UpperBound : Endpoint<'a> }`

Such a record type is also easily identified as a product type. In a sense, we can think of a record type as a 'tuple with metadata', where the metadata contains *names* of elements.

In C# `Range<T>`

is a class with two `Endpoint<T>`

fields.

private readonly Endpoint<T> min; private readonly Endpoint<T> max; public Range(Endpoint<T> min, Endpoint<T> max) { this.min = min; this.max = max; }

In a sense, you can think of such an immutable class as equivalent to a record type, only requiring substantial ceremony. The point is that because a range is a product of two functors, it itself gives rise to a functor. You can see all the implementations in Range as a functor.

### Binary tree Zipper #

In A Binary Tree Zipper in C# you saw that the `BinaryTreeZipper<T>`

class has two class fields:

public BinaryTree<T> Tree { get; } public IEnumerable<Crumb<T>> Breadcrumbs { get; }

Both have the same generic type parameter `T`

, so the question is whether `BinaryTreeZipper<T>`

may form a functor? We now know that the answer is affirmative if `BinaryTree<T>`

and `IEnumerable<Crumb<T>>`

are both functors.

For now, believe me when I claim that this is the case. This means that you can add a `Select`

method to the class:

public BinaryTreeZipper<TResult> Select<TResult>(Func<T, TResult> selector) { return new BinaryTreeZipper<TResult>( Tree.Select(selector), Breadcrumbs.Select(c => c.Select(selector))); }

By now, this should hardly be surprising: Call `Select`

on each constituent functor and create a proper return value from the results.

### Higher arities #

All examples have involved products of only two functors, but the result generalizes to higher arities. To gain an understanding of why, consider that it's always possible to rewrite tuples of higher arities as nested pairs. As an example, a triple like `(42, "foo", True)`

can be rewritten as `(42, ("foo", True))`

without loss of information. The latter representation is a pair (a two-tuple) where the first element is `42`

, but the second element is another pair. These two representations are isomorphic, meaning that we can go back and forth without losing data.

By induction you can generalize this result to any arity. The point is that the only data type you need to describe a product is a pair.

Haskell's base library defines a specialized container called Product for this very purpose: If you have two `Functor`

instances, you can `Pair`

them up, and they become a single `Functor`

.

Let's start with a `Pair`

of `Maybe`

and a list:

ghci> Pair (Just "foo") ["bar", "baz", "qux"] Pair (Just "foo") ["bar","baz","qux"]

This is a single 'object', if you will, that composes those two `Functor`

instances. This means that you can map over it:

ghci> elem 'b' <$> Pair (Just "foo") ["bar", "baz", "qux"] Pair (Just False) [True,True,False]

Here I've used the infix `<$>`

operator as an alternative to `fmap`

. By composing with `elem 'b'`

, I'm asking every value inside the container whether or not it contains the character `b`

. The `Maybe`

value doesn't, while the first two list elements do.

If you want to compose three, rather than two, `Functor`

instances, you just nest the `Pairs`

, just like you can nest tuples:

ghci> elem 'b' <$> Pair (Identity "quux") (Pair (Just "foo") ["bar", "baz", "qux"]) Pair (Identity False) (Pair (Just False) [True,True,False])

This example now introduces the `Identity`

container as a third `Functor`

instance. I could have used any other `Functor`

instance instead of `Identity`

, but some of them are more awkward to create or display. For example, the Reader or State functors have no `Show`

instances in Haskell, meaning that GHCi doesn't know how to print them as values. Other `Functor`

instances didn't work as well for the example, since they tend to be more awkward to create. As an example, any non-trivial Tree requires substantial editor space to express.

### Conclusion #

A product of functors may itself be made a functor. The examples shown in this article are all constrained to two functors, but if you have a product of three, four, or more functors, that product 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 products into functors, in the way that Haskell's `Product`

container almost does. Thus, knowing when you can safely give your generic types a `Select`

method or `map`

function may come in handy.

There are more rules like this one. The next article examines another.

**Next:** Functor sums.