Functors

For those of you that love math, the notion of a functor in Haskell is exactly the same as an endofunctor in the category of Haskell types.¹ Pragmatically, to effectively program using functors and the other abstractions we will discuss soon, you don't need to understand what this sentence means; you can ignore it. I programmed effectively in Haskell for about 10 years before I finally opened a category theory book to understand the connection between Haskell functors and categorial functors, between Haskell monads and categorial monads, and so on.

To start, a functor is a type constructor with a single argument, and we can view it as a container storing values of this argument type. This includes

Lists: The list type [a] can be viewed as passing the type of the list elements a to the type constructor []. Maybe our earlier home-baked version of lists makes this a bit clearer. Those lists had the type List a, so List is a type constructor with a single argument a. A list is also clearly a container type.
Arrays: Arrays in Haskell have the type Array i e. They are parameterized by two types. i is the type used to index into the array. e is the type of elements stored in the array. If we fix the first type argument, i, to Int, for example, we obtain Array Int e. This is still a type constructor, because we can still substitute anything for e. So the partially applied type constructor Array Int takes a single argument e and produces from it an array type. Arrays are also containers.
Maybe: It certainly fits the bill. Maybe a takes a single type argument a. However, how is it a container? We can look at Maybe as a very simple sort of container. If we have a container of type Maybe a that is Just x, then it stores a single value x. If it is Nothing, then it stores, well, nothing. So we can think about Maybe as a container type that can store 0 or 1 elements.
Identity: Identity a is a container that stores exactly one value of type a. Here's the definition:
```
newtype Identity a = Indentity a
```
This functor will play an important role towards the end of the next chapter, when we discuss monad transformers.
Binary trees: We can define a type
```
data Tree a = Empty | Node (Tree a) a (Tree a)
```
This says that a binary tree storing values of type a is either Empty or consists of a root Node that stores some value of type a and with a left and right subtree of type Tree a. Again, this matches our notion of a container—the tree stores some values in its nodes—and the type constructor Tree a takes a single argument.
Functions that produce an a:
```
newtype Reader r a = Reader { runReader :: r -> a }
```
Just as with arrays, this type constructor takes two arguments. We can fix the first one to, say, Int. This gives Reader Int a, which is a type constructor with a single argument left to fill in. So Reader Int is a candidate to be a functor. How is it a container though? It clearly doesn't store any values of type a, only a function of type Int -> a.

But what's a function of type Int -> a? One way to think about it is as a container that stores a whole bunch of as indexed by Int values. Given a specific Int value, applying the function to it "retrieves" the corresponding a value.

So our notion of containers is more conceptual than physical. The values of type a "stored" in the container don't have to be physically present, in the sense that they occupy some space in memory, but they must be retrievable in some fashion.

There are many more type constructors that are functors, but this list should suffice for now. You should look at all of them as container types, even though you may have to squint a bit to see how exactly they "contain" values.

Many container types are functors, but not all are. To be a functor, a container must be "well-behaved" in the sense discussed next.

This has the caveat that there is some debate whether Haskell types even form a true category, but even if they don't, the abstractions defined in category theory applied to something that's almost a category gets us very far when trying to bring order to the wealth of programming abstractions we use every day. ↩