Functortown: Functor and Bifunctor
This series covers the two most basic functor typeclasses in Haskell:
Bifunctor. Understanding these two typeclasses, how
bimap work, their laws, and why all this exists is at the very heart of understanding not just all the rest of the functors, from monads to profunctors, but is fundamental to understanding Haskell itself because of how it helps us to understand typeclasses and the promise (and deficiencies) of reusable code via abstractions.
- knowledge of several basic types, especially
Either, tuples, and the function type;
- basic understanding of typeclasses and their relationship with types; and
- some facility with Haskell syntax.
The series itself starts with an example rather than definitions, and particularly if you’re new to functors or to Haskell, we recommend you start by jumping into that and come back to read the rest of this page later. The rest of this page serves as reference and context, largely for readers who already have some concrete familiarity with these two typeclasses.
Definitions and documentation
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
Functor class declaration looks like this.Documentation for the
Functor class and instances.
- This signature for
ftells us this is a typeclass for type constructors of kind `* -> *`.
- The polymorphic type of its one principal method, called
- An auxiliary method of the class, derivable from the implementation of
MINIMALline tells us which of the methods we must implement in order to have an
instanceof 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
Either and the pair or two-tuple are prototypical bifunctors, and the reason we link
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.
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.
- This line calls the bifunctor in question
pand tells us it has kind `* -> * -> *`, which means it has two type parameters.
- The polymorphic type of
bimap, one of the principal methods of this class.
- The polymorphic type of
first, one of the principal methods of this class.
- The polymorphic type of
second, one of the principal methods of this class.
MINIMALline tells us which methods we need to implement in order to have a complete
The compiler can derive an implementation of
bimap from implementations of
second, or vice versa, so you don’t need to write all three.
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
If you implement
second, then you must concern yourself with their identity laws, the meaning of which is the same as the identity laws for
If you supply both, you should also ensure that your implementations of
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
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.
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
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
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
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
Maybecontext? We solve it by writing the function we need and then discuss generalizing that function for other contexts. Finally, we briefly discuss the
mapfunction for lists.
More common functors – This starts with some examples of using the
IOfunctor. Then we introduce product types and tuples and the
Functorinstance 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
Functorclass 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
Breaking the laws! – Here we start with a discussion of why typeclass laws matter before diving into the
Functorlaws, and we introduce using the
hedgehogtesting 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
Bifunctoroffers 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
Eitherbifunctor and look at an interesting bifunctor from the
thesepackage and some of its related typeclasses.
The laws of the bifunctors – We conclude our discussion of
Bifunctorby talking about its laws and, again, property testing instances to ensure they obey the laws, using the
hedgehoglibrary. This lesson also includes some extra information about the
hedgehoglibrary and how it works.