Functortown: Functor and Bifunctor

Our teaching philosophy prioritizes working from concrete to abstract, and therefore this series starts from a motivating example rather than from a definition of terms. What it means to be a functor or a bifunctor is something that should be made apparent through the examples and discussion. However, sometimes you just need a reference page to remind yourself of one thing or another. Additionally, there is something satisfying in being able to give a brief definition, to ensure we really have the concept within our grasp. That’s what this section is for.

A functor is a type constructor that has one type argument We call these unary type constructors. Examples include Maybe and lists – Maybe and list both have a single type parameter (usually called a, as in Maybe a and [a]). and supports a (law-abiding) mapping operation called fmap. You may have heard in the past that functors are containers. We prefer to think of them as constructors or contexts, rather than containers, although this distinction is not critical, in our view. At any rate, the container idea comes from the fact that lists and their various analogs are in many ways prototypical functors, and in many languages that operation is simply called map. Haskell, too, has a map functionData.List.map in its base libraries, and for type constructors like Set that don’t support a law-abiding fmap, the implementation of the mapping operationData.Set.map is often called map.

The Functor class declaration looks like this.Documentation for the Functor class and instances.

1. This signature for f tells us this is a typeclass for type constructors of kind * -> *.
2. The polymorphic type of its one principal method, called fmap.
3. An auxiliary method of the class, derivable from the implementation of fmap.
4. The MINIMAL line tells us which of the methods we must implement in order to have an instance of the class.

What the code doesn’t say is that to have a good Functor, the implementation of fmap should abide by the two Functor laws: identity and composition. The compiler has no way to enforce this, but the laws are there to ensure that the behavior of fmap in any code, for whatever type, is predictable. The identity law says

That is, mapping an identity function over a value should be exactly the same as applying the identity function directly to that value.

And the composition law says

That is, mapping the composition of two functions over a value should be exactly the same as composing the mappings of the two functions over that value.

A bifunctor is a functor that has two type arguments that can be mapped over – or, a functor that can support a (lawful) implementation of a mapping operation called bimap. Either and the pair or two-tuple are prototypical bifunctors, and the reason we link Functor and Bifunctor in this series is that Bifunctor provides the answer to some very common questions about the Either and tuple Functors without adding much additional complexity.

The Bifunctor class is in the base library but not in the Prelude that is automatically in scope in all your GHCi sessions and what have you. Because it is in the base library, though, you can import it by typing import Data.Bifunctor in any file or into a GHCi session without adding a dependency. The class definition looks like this.Documentation for the Bifunctor class and instances.

1. This line calls the bifunctor in question p and tells us it has kind * -> * -> *, which means it has two type parameters.
2. The polymorphic type of bimap, one of the principal methods of this class.
3. The polymorphic type of first, one of the principal methods of this class.
4. The polymorphic type of second, one of the principal methods of this class.
5. The MINIMAL line tells us which methods we need to implement in order to have a complete instance:

• bimap OR
• first and second.

The compiler can derive an implementation of bimap from implementations of first and second, or vice versa, so you don’t need to write all three.

As with Functor, the Bifunctor class has some laws that a good Haskeller should not ignore.

First there are identity laws. If you implement bimap, then it’s the bimap identity that should concern you.

As with the Functor identity law above, this says that the application of bimap id id to a value should give the same result as applying just id to the same value, as in

λ> bimap id id (22, "julie")
(22,"julie")

λ> id (22, "julie")
(22,"julie")

If you implement first and second, then you must concern yourself with their identity laws, the meaning of which is the same as the identity laws for bimap or fmap.

If you supply both, you should also ensure that your implementations of bimap and first and second relate to each other in a predictable way.

That is, the bimapping of two functions should be the same as the composition of mapping the two functions over their respective values.

The Hackage documentation goes on to assert that the following laws “ensure by parametricity”:

These should all look familiar, as they are the Bifunctor versions of the Functor composition law. A detailed explanation of what it means that they “ensure by parametricity” is out of the current scope of this reference page, so we’ll attempt an intuitive sort of explanation. The generality of fmap and bimap that we see in their types, that they have to be true for all functions (a -> b), means that what those functions can do to the structure of the data is very tightly constrained. So it doesn’t matter whether we compose the two functions first and then map them, or we compose the two mappings. Parametric polymorphism constrains what the mapped functions can do in such a way that the order in which we map versus compose the functions can’t change the results.

The Functor class is one of the standard classesSee Section 6.3 of the Haskell Report 2010. The section number (6.3) is the same for the Haskell 98 report. defined in the Haskell Report. Both the 1998 and 2010 versions of the Report give a very short definition of the class, a brief statement of the laws, and the list of standard instances of the class: Maybe, lists, and IO.

The idea of a functor, however, is much older than Haskell. While the word ‘functor’ does not originate in mathematics, Haskell borrowed both the word and the concept from a branch of mathematics called category theory. Haskell’s functors work more or less the same as category theory functors, but it is not necessary to know anything about the mathematical functors in order to understand Haskell.

Bifunctor was, until recently, not part of the standard library. It started as part of the bifunctors package by Edward Kmett, part of a system of libraries that is lovingly referred to by Haskellers as the “Kmettiverse”. The bifunctors package still exists and is maintained, because only a portion of it was merged into the base library.The bifunctors package. The Data.Bifunctor module was added to base with the 4.8 release, which corresponds to GHC 7.10.1 release.

Most often, bifunctors are not presented as introductory Haskell material, largely, in our opinion, due to this historical accident. If you understand fmap, it seems to us only a small stretch to understand bimap. And Bifunctor helpfully answers one of the most common questions that people new to Haskell have about Functor: how can I use fmap to apply a function to that first value in a tuple, or the Left of an Either. So we’ve included bifunctors in this first series.

• Introduction to mapping – This introduces a problem: how can we apply a function to a value that is embedded within a Maybe context? We solve it by writing the function we need and then discuss generalizing that function for other contexts. Finally, we briefly discuss the map function for lists.

• More common functors – This starts with some examples of using the IO functor. Then we introduce product types and tuples and the Functor instance for two- and three-tuples, comparing them along the way to a type that is similar to a tuple but different in an important way.

• Laws and orders – This lesson goes deeper into the nature of the Functor class by looking at how the ordering of type parameters matters and a perfectly good container type that isn’t a Functor (and why). We also cover the function Functor.

• Breaking the laws! – Here we start with a discussion of why typeclass laws matter before diving into the Functor laws, and we introduce using the hedgehog testing library to property test some good instances and some not so good instances.

• Two maps in one – Here we continue a discussion from the previous lesson and show how Bifunctor offers a tidy solution to the problem we had. The lesson continues with a discussion of what bifunctors are and what covariant means.

• More than a sum – This lesson takes a small detour to extend what we know about the Either bifunctor and look at an interesting bifunctor from the these package and some of its related typeclasses.

• The laws of the bifunctors – We conclude our discussion of Bifunctor by talking about its laws and, again, property testing instances to ensure they obey the laws, using the hedgehog library. This lesson also includes some extra information about the hedgehog library and how it works.