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
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 `* -> * -> *`)

``````instance Functor (Either e) where