Road to monads: Functors

Introduction

In this series I plan on writing about various Haskell/functional programming things that contribute towards [understanding monads][1]. I want to take a different approach than an all-in-one information overload style that I see in just about every monad tutorial I read. A lot of people apply analogy exclusively to explain what monads are or what they are used for, but I think this approach is limited as analogy itself is flawed. Instead, I’ll aim to take an approach by going through the functions.

Understanding functors is the first step towards understanding monads.

What is a functor?

A functor in Haskell is a bit of data with something else attached to it: a type that can be mapped over. I like to think of this as a context and a value:

f a => f is the context, a is the value

Just 12 => Maybe is the context, 12 is the value

[27] => [] is the context, 27 is the value

Definition

Functors have the following typeclass:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

So a functor is just something which implements fmap (which is a more general version of map, but functor-map).

It takes a function (a -> b), and lifts it into the context of the functor f before applying it to a, returning a value in the context of the original functor: f b.

Functor laws

Functors have an identity law and a composition law:

fmap id = id
fmap (p . q) = (fmap p) . (fmap q)

The identity law means that applying id to the value of the functor and then attaching its context is the same as applying id to the context and value together.

The composition law means that when lifting functions to work in a functor’s context, it doesn’t matter if those functions are composed before being lifted (p . q), or if those functions are lifted individually and then composed (fmap p) . (fmap q).

Standard functors

Maybe

Maybe is for things which are either Just there, otherwise Nothing is there. Its context is optional values.

Here are some types:

λ: :t Just 3
Just 3 :: Num a => Maybe a
λ: :t Just 'a'
Just 'a' :: Maybe Char
λ: :t Nothing
Nothing :: Maybe a

So Maybe is a type constructor; put a type after it to form a concrete type: Maybe Int. Nothing is always abstract though, because through polymorphism, it can act as any type of Maybe concrete type: Nothing :: Maybe a where a can be Int, Char or anything else.

The Functor instance for Maybe looks like this:

instance Functor Maybe where
  fmap _ Nothing       = Nothing
  fmap f (Just a)      = Just (f a)

So fmap applies a given function inside a Just, or returns Nothing if Nothing was there already:

λ: fmap (+1) (Just 2)
Just 3
λ: fmap (*3) (Just 4)
Just 12
λ: fmap (+1) Nothing
Nothing

List

Lists represent the context of non-deterministic (compute all possible values) evaluation, as they can contain multiple homogeneous values:

λ: :t []
[] :: [t]
λ: :t ['a']
['a'] :: [Char]
λ: :t [2, 3, 5, 7, 11]
[2, 3, 5, 7, 11] :: Num t => [t]

[] is the constructor here, and the : operator is used to prepend to it. [1, 2, 3] is actually syntactic sugar for 1 : 2 : 3 : []:

λ: 1 : 2 : 3 : []
[1,2,3]

fmap for lists is actually just implemented with map:

instance Functor [] where
  fmap = map

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

This takes a function and applies it to each element in the list, returning a list of results:

λ: map (*12) [1..9]
[12,24,36,48,60,72,84,96,108]
λ: map (+1) []
[]

->

Composition is a functor, because functions can have functions mapped over them as per the rules of composition. The context here is function composition, which means that logically, as long as the types line up, two functions can be “joined together” via composition, and values are the functions themselves.

λ: :t (+1)
(+1) :: Num a => a -> a
λ: :t head
head :: [a] -> a
λ: :t id
id :: a -> a

fmap for functions is implemented using the . function composition operator:

instance Functor ((->) r) where
  fmap = (.)

r is necessary because (->) has a kind of * -> * -> *, which means that it needs two types to turn it into a concrete type. We give it the polymorphic type r, and currying means that (->) r has the kind * -> *:

λ: :k (->)
(->) :: * -> * -> *
λ: :k ((->) Int)
((->) Int) :: * -> *

Function composition takes two functions f and g, where the domain of f is the codomain (range) of g and joins them together f . g to form a third function which would be identical to applying g and then f to a value. In Haskell, the domains we care about are types:

λ: :t (+1)
(+1) :: Num a => a -> a
λ: :t (*2)
(*2) :: Num a => a -> a
λ: :t not
not :: Bool -> Bool

λ: :t ((+1) `fmap` (*2))
((+1) `fmap` (*2)) :: Num a => a -> a
λ: ((+1) `fmap` (*2)) 2
5
-- Composition is not commutative
-- f . g /= g . f
λ: ((*2) `fmap` (+1)) 2
6

-- Here's what happens when we try to compose functions where the types don't
-- match
λ: :t (not `fmap` (*2))

<interactive>:1:14:
  No instance for (Num Bool) arising from a use of ‘*’
  In the second argument of ‘fmap’, namely ‘(* 2)’
  In the expression: (not `fmap` (* 2))

Either

Either is a Left or a Right, where Left and Right can be different types. It’s Haskell convention to put correct values in the Right constructor, because if something is right it is correct.

λ: :t Left 1
Left 1 :: Num a => Either a b
λ: :t Right "abc"
Right "abc" :: Either a [Char]

-- A function which returns True when given 2, or an error message elsewise
twoOrError :: Integer -> Either String Bool
twoOrError 2 = Right True
twoOrError _ = Left "Didn't get a 2!"

λ: twoOrError 2
Right True
λ: twoOrError 3
Left "Didn't get a 2!"

For Either, fmap is implemented in such a way that it will apply its given function to Right values, but leave Left values alone:

not :: Bool -> Bool
not True = False
not False = True

λ: fmap not (twoOrError 2)
Right False
λ: fmap not (twoOrError 3)
Left "Didn't get a 2!"

Try to work out the implementation of fmap for the Either typeclass as a reader exercise.

(Hint: Either has a kind * -> * -> *)

Answer:

instance Functor (Either e) where
  fmap _ (Left l) = Left l
  fmap f (Right r) = Right (f r)