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