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 - butmap is limited to the type of lists, whereas fmap can be used with any parameterised type that uses a type constructorf, 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.