Functor Laws

To be a functor, a container f needs to support a function fmap :: (a -> b) -> f a -> f b. fmap takes two arguments, a function g :: a -> b and a container xs :: f a.¹ It returns a container of type f b. Note the change in element type matching exactly the transformation from type a to type b implemented by g. The container produced by fmap g xs has exactly the same "shape" as xs. The only thing fmap does is to replace every element in xs with the result of applying g to it. The following figure illustrates this for binary trees:

Illustration of fmap applied to a tree — Applying `fmap` to a tree does not change the "shape" of the tree: the number of nodes remains the same, as does their parent-child relationships. All that is changed is that the value stored at each node is replaced with the result of applying the given function to it.

Haskell does not give us the tools to express that an application of fmap to a container xs should produce a container of the same "shape" as xs. It is our responsibility as a programmer to ensure that this is the case if we declare a container type to be a functor. Specifically, we need to ensure that the container satisfies the two functor laws (taken straight from category theory) discussed below.

We declare a container type f to be a functor by making it an instance of the following type class.

class Functor f where
    fmap :: (a -> b) -> f a -> f b
    (<$) :: b        -> f a -> f b
    (<$) = fmap . const

We already discussed what fmap should do. (<$) is a specialized version of fmap. y <$ xs doesn't really apply a function to every element in xs. It simply replaces every element in xs with y. The default implementation achieves this using the const function, which is useful in various contexts:

const :: a -> b -> a
const x _ = x

Viewed as a two-argument function, const ignores its second argument and simply returns its first argument. It's more illuminating to look at the partially applied function const 5, for example. This is a one-argument function that ignores its argument and always returns 5. It's a constant function. Hence the name const. Thus, fmap (const y) xs applies const y to every element in xs. This simply replaces each element with y. The definition y <$ xs = fmap (const y) xs thus does the right thing. We obtain the above point-free definition via simple rewriting:

y <$ xs   = fmap (const y) xs
(<$) y xs = fmap (const y) xs    -- Switch to using <$ in prefix position
(<$) y    = famp (const y)       -- Drop the common argument xs because two
                                 -- functions are equal if and only if they
                                 -- produce the same result for every possible
                                 -- argument.
(<$) y    = (fmap . const) y     -- Use the definition of function composition:
                                 -- (f . g) x = f (g x)
(<$)      = fmap . const         -- Drop the common argument y

So what are the functor laws then? There are two of them:

Identity law:
```
fmap id = id
```
id is the identity function that simply returns its argument:
```
id :: a -> a
id x = x
```
So the identity law says that if we apply the identity function to every element in a container, we get the original container back: fmap id is itself the identify function for containers. This captures the idea that fmap f xs should produce a container of the same shape as xs: fmap is not allowed to change the shape of the container. Applying id to every element in the container replaces the element with itself, so it doesn't change anything either. Put together, fmap id xs does not change anything; it just produces xs. fmap id = id.
Composition law:
```
fmap (f . g) = fmap f . fmap g
```
This says that applying the composition of two functions f . g to every element in a container should produce the same result as first applying g to every element in the container and then applying f to every element in the resulting container.

As a concrete example, if we take a list of as, then we can either directly produce a list of cs by applying the function f . g to each element in the input list, or we can first produce a list of bs by applying the function g to each element in the input list, and then turn this into a list of cs by applying the function f to each element in the list this produces. Both results must be the same:
GHCi
```
>>> add1 x = x + 1
>>> double x = 2 * x
>>> fmap (add1 . double) [1,2,3]
[3,5,7]
>>> fmap double [1,2,3]
[2,4,6]
>>> fmap add1 [2,4,6]
[3,5,7]
>>> (fmap add1 . fmap double) [1,2,3]
[3,5,7]
```

Transforming containers by applying functions to their elements is a common pattern in programming, so it is nice to have it captured by the fmap function of the Functor type class. Let's see how we can implement fmap for different container types.

Ugh, this is starting to turn into symbol salad. How exactly is f a a type? Remember, that we want f to be an arbitrary container type, and a to be the type of the values we store in the container. If we set f = Tree and a = Int, we obtain a Tree Int, a tree of integers. This should be less confusing. In general, Tree a is a tree storing values of type a. Here, we generalize this further to have an f a, a container of type f that stores values of type a. ↩