Bifunctors in TypeScript
Exploring the extended functor family part II
This is the second installment into the series on lesser-known abstractions in functional programming with TypeScript. The first part can be found here. In this article I will amuse you understand the concept of covariant and contravariant functors, so consider reading the first part before this one if those terms don’t ring a bell.
This time we will look at functors that show up when using type algebra to combine types. Type algebra is an important and common concept in functional programming, as are the functors that exists as a result of it. You will see that many of the well-known (monadic) abstractions are in fact defined by type algebra and are bifunctors.
The bifunctor
As the name suggests a ‘bi’-functor is a functor that is actually two functors. A bifunctor is a type that has two covariant type arguments. The two primary cases are the sum and product types. A Pair is the easiest example of a type that contains two other types:
The other classic example is the Sum type. While the instance does only contain an instance of one of the two types, the type contains two arguments in a positive position:
There are various standard functors based on based on Sum and Pair types: Either, Result and Option to name some for sum types and Writer and State for product types. For them to work as a functor we always have to fix one of the type arguments, which can sometimes be limiting. For example, Result always has to keep same error type when using fmap or bind. Luckily for us there exists a type of functor that works on two covariant type arguments: the bifunctor.
A bifunctor defines three functions: bmap for mapping both of the arguments, lmap for only mapping the left argument and rmap for only mapping the right argument. Note that rmap is the same as fmap, meaning that every bifunctor is also a covariant functor. So when using type algebra you are not just getting bifunctors for free, but also normal functors. Those functions can be described in an interface:
Implementing bifunctors
To make all of the above theory more practical I have written an implementation of Either in TypeScript. Note that fmap and lmap are for both the left and right side the same.
Based on this definition we can directly define some concrete and powerful functors by just using aliases. The first is Option. An option is nothing more than a Either of Unit and a. And the constructors (none and some) are also just aliases for left and right. Sadly we cannot say none = left in TypeScript because of the limitations in the type inference with regards to generic type arguments, so we have to create actual functions to put the type arguments around it.
Another monad who is derived from Either is Result. This one we can also define in only aliases of the Either functor:
Product types also make a bifunctor. Shown below is the definitions of Pair as a bifunctor and the implementation of a StringWriter based on a definition of Pair.
One could wonder if we could define a binary variant of our contravaraint functor. And the answer is yes, we can. But in practice the covariant functor is only one that gets defined as a bifunctor because it is a common structure where binary variants of the other functors are very rare.
The bifunctor laws
As all functors, a bifunctor has to follow an indentity law that enforces the pureness of the map function. For the bifunctor this is defined with passing the identity function twice to bmap.
b.bmap(id)(id) == id(b) == b
The next law describes the behaviour of lmap and rmap. lmap should leave the second type argument alone and rmap the first one. This can be described with the bmap function that has one of its arguments set to id.
b.bmap(f)(id) == b.lmap(f)
b.bmap(id)(g) == b.rmap(g) == b.fmap(g)
The last law is the composition law. Like all the other functors, call the map function with the composition of two function should equal calling the mapping function twice for both functions:
b.bmap(f1)(g1).bmap(f2)(g2) == b.map(a => compose(f1, g1))(compose(f2, g2))
compose is here a function that composes g after f, defined in TypeScript like this:
Conclusion
In this article we have seen how type algebra creates a special kind of functor. This functor turns out to be one of the most powerful functors, powering among others railroad programming, options and state monads. If you haven’t read the previous article in this series you can find it here.
