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.
