# Functors

**Functors*** *generalise the idea of

**function mapping**on a data structure type, i.e. applying a function to each element in the data structure. We have looked at the

`map`

function that does exactly that but is limited to a specific data structure - `list`

. However, any **parameterised**

**type**

*(data structure) can be made into an instance of the*

`functor`

class so that it supports function mapping to its elements through the use of the `fmap`

function:The `(<$)`

function simply replaces all elements in the data structure with the given value `a.`

Comparing `fmap`

to `map`

:

We can see that `fmap`

has the exact same type signature as `map`

- but`map`

is limited to the type of `lists`

, whereas `fmap`

can be used with any parameterised type that uses a *type constructor*`f`

, i.e. is a class of `Functor f`

. Note that the form of`[a]`

and `[b]`

is just syntax sugar for the list type and is equivalent to `[] a`

and `[] b`

, where `[]`

is the *type constructor* for the list type.

Since the `map`

and `fmap`

functions perform the same action, it is very simple to make the `list`

type into a functor (and it is made into one by default) by using the `instance` keyword:

However, when it comes to other data structure types, we have to define the `fmap`

function ourselves. For example, the `Maybe`

type (also an instance of the `Functor`

class by default) can be made an instance of the `Functor`

class as:

In the case of a `Nothing`

, we ignore the function and return `Nothing`

as `Nothing`

generally represents an error state that we want to propagate through our `fmap`

function as well. Otherwise, we apply the function `f`

to the underlying value `x`

of `Just x`

and return the `Maybe`

type (using the `Just`

constructor) of the result, i.e. the function application `f x`

.

Now let's see how we can make a newly-defined data type into an instance of the `Functor`

class. We will first define a data type `Tree`

that will represent a full **binary tree**. A full binary tree is a binary tree type in which every tree node has either `0`

or `2`

children. In our case, a node with `0`

children will be a `Leaf`

that stores some value, and a node with `2`

children will be a `Branch`

that branches into two new nodes without storing a value itself:

And now, we want to make `Tree`

a functor, so we have to define the `fmap`

function for it:

The first case of `Leaf`

is analogous to how we defined the `Just`

case of the `Maybe`

functor - we apply the function `f`

to the underlying value `x`

and return it wrapped in the `Leaf`

constructor. In the other case, where we are dealing with a `Branch`

we recursively apply `fmap`

to both children nodes of the branch.

To represent the following binary tree:

We can use the following code and `fmap`

over the entire data structure, applying the specified function (in this case `(/2)`

) to each leaf:

Note that the `Prelude`

comes with an infix operator for `fmap`

as well - `(<$>)`

, not to be confused with the function application operator, `($)`

:

`($)`

is the simple function application operator we learned about before, while `(<$>)`

is *also a function application operator* but with lifting over a Functor. We could also write the above code as:

## Functor Laws

There are two functor laws that must be satisfied to ensure that `fmap`

works as intended:

The `id`

is the identity function, and it is used to simply return the unaltered argument passed in. This means that mapping the `id`

function over a structure should return the same structure back unaltered.

The second functor law ensures that *function* *composition* is preserved when using `fmap`

so that it does not matter whether we map a composed function `(g . f)`

or map the first function `g`

and then the second function `f`

, as long as the order of the `g`

and `f`

functions stays the same.

Last updated