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))
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.