# 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:

``````class Functor f where
fmap :: (a -> b) -> f a -> f b
(<\$) :: a -> f b -> f a

-- Minimal complete definition:
-- fmap``````

The `(<\$)` function simply replaces all elements in the data structure with the given value `a.`

Comparing `fmap` to `map`:

``map :: (a -> b) -> [a] -> [b]``

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:

``````instance Functor [] where
-- fmap :: (a -> b) -> [] a -> [] b
fmap = map``````

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:

``````instance Functor Maybe where
-- fmap :: (a -> b) -> Maybe a -> Maybe b
fmap _ Nothing = Nothing
fmap f (Just x) = Just (f x)``````

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:

``````data Tree a = Leaf a | Branch (Tree a) (Tree a)
deriving (Show)``````

And now, we want to make `Tree` a functor, so we have to define the `fmap` function for it:

``````instance Functor Tree where
-- fmap :: (a -> b) -> Tree a -> Tree b
fmap f (Leaf x) = Leaf (f x)
fmap f (Branch l r) = Branch (fmap f l) (fmap f r) ``````

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:

``````ghci> myTree = (Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 10) (Leaf 20)))
ghci> fmap (/2) myTree

Branch (Branch (Leaf 0.5) (Leaf 1.0)) (Branch (Leaf 5.0) (Leaf 10.0))``````

Note that the `Prelude` comes with an infix operator for `fmap` as well - `(<\$>)`, not to be confused with the function application operator, `(\$)`:

`````` (\$)  :: (a -> b) -> a -> b

(<\$>) :: Functor f => (a -> b) -> f a -> f b
(<\$>) = fmap``````

`(\$)` 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:

``````ghci> myTree = (Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 10) (Leaf 20)))
ghci> (/2) <\$> myTree

Branch (Branch (Leaf 0.5) (Leaf 1.0)) (Branch (Leaf 5.0) (Leaf 10.0))``````

## Functor Laws

There are two functor laws that must be satisfied to ensure that `fmap` works as intended:

``fmap id = id``

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.

``fmap (g . f) = fmap g . fmap f``

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