`data Maybe a = Nothing`

| Just a

`data Maybe a = Nothing`

| Just a

class Functor f where

fmap :: (a -> b) -> f a -> f b

instance Functor Maybe where

fmap _ Nothing = Nothing

fmap f (Just a) = Just (f a)

We have a polymorphic type `f`

, and `fmap`

gives us the ability to:

Liberate a pure value from the type constructor that refers to it

Call a function on it, which could return a result of a different type

Have the type constructor refer to the type of the result

That polymorphic type `f`

was daunting to me when I was learning Haskell.

The easiest easy to *begin* to think of `f`

is as a "container".

Here is the most basic of containers:

`newtype Container a = Container a`

instance Functor Container where

fmap f (Container a) = Container (f a)

We can't get any simpler than this, since (being a `newtype`

) it doesn't have a runtime representation at all.

`instance Functor Container where`

fmap f (Container a) = Container (f a)

instance Functor Maybe where

fmap _ Nothing = Nothing

fmap f (Just a) = Just (f a)

instance Functor [] where

fmap = map

Having seen these instances, we can now state with some confidence:

For a container type,

`fmap`

replaces every element of the container with the result of applying`f`

to that element.It leaves the

*structure*of the container unchanged.

In other words, `fmap`

will not turn a `Just`

into a `Nothing`

, or a 3-element list into an empty list, or the like.

As useful as this intuitive picture is, it's actually not general enough.

We'd be making a mistake if we thought we had the whole story now, because the truth is far richer (and stranger).

Let's poke about in `ghci`

:

`>> :type not`

not :: Bool -> Bool

Remember that the `->`

symbol is not magic: it's just a type constructor.

Using a notational shortcut, we could rewrite the type above as:

`(->) Bool Bool`

If we get rid of the concrete types and replace them with polymorphic placeholders, we can write a type signature like this:

`(->) a b`

Okay, so we know that this is a function type:

`(->)`

And this is a function that accepts an argument of some type `a`

, and gives a result of some other type `b`

:

`(->) a b`

So then what's this?

`(->) a`

This type, being a function that accepts an argument of type `a`

, is polymorphic. (Why?)

`((->) a)`

Which suggests that even though it's surely not a container type, we could write a `Functor`

instance.

`instance Functor ((->) a) where`

fmap f {- ...what? -}

On the whiteboard, let's puzzle through what the `Functor`

instance ought to look like.

`instance Functor ((->) a) where`

fmap f {- ...what? -}

Because here's that definition we were scrawling on the whiteboard.

`instance Functor ((->) a) where`

fmap f g = \x -> f (g x)

Which we can simplify to:

`instance Functor ((->) a) where`

fmap f g = f . g

And again:

`instance Functor ((->) a) where`

fmap = (.)

Function application is somehow a functor?

I know, right!?

Let's play with that in `ghci`

a bit.

A functor (in Haskell) is simply a pair of things:

A polymorphic type

A definition for

`fmap`

The instance has to obey two simple laws:

`fmap id == id`

fmap (f . g) == fmap f . fmap g

As usual with laws, it's up to you as a coder to satisfy the laws with your `Functor`

instances.

In the `Control.Applicative`

package we'll find another extremely useful typeclass:

`class Functor f => Applicative f where`

pure :: a -> f a

(<*>) :: f (a -> b) -> f a -> f b

The `Applicative`

class builds on functors to add two very useful new behaviours.

The

`pure`

operator lifts a normal value into the type.The

`<*>`

operator sequences function application through the type.

If those definitions feel slippery, remember the signature for `fmap`

:

`fmap :: (a -> b) -> f a -> f b`

The only difference between `fmap`

and `<*>`

is that `<*>`

starts off with the function wrapped in the type `f`

.

`(<*>) :: f (a -> b) -> f a -> f b`

This is easiest to follow with a concrete example.

`instance Applicative Maybe where`

pure = Just

Just f <*> Just a = Just (f a)

_ <*> _ = Nothing

Which of these questions is easier to answer?

"I'm thinking of a number. It's less than 5."

"I'm thinking of a number. It's less than 5. It's greater than zero."

By adding more information, we've constrained the possible numbers available to be guessed.

We can loosely carry this line of thinking over to typeclasses:

The more functions a typeclass has, the more constraints there are on the types that can possibly implement it.

The more laws an instance must satisfy, the smaller the number of types that can satisfy them.

To keep those brains nice and groovy, let's look at how function application lives as an `Applicative`

.

`instance Applicative ((->) a) where`

pure x = \_ -> x

f <*> g = \x -> f x (g x)

The `Functor`

class has one method and two laws.

The `Applicative`

class adds two methods and four laws (the laws are simple and intuitive, but I'm not going to describe them).

By appeal to my prior handwaving, the added richness of `Applicative`

comes at a cost:

- There exist many more types that we can turn into functors than into applicatives.

That richness is appealing though: we'll take it when we can. (But I'm not going to explain why just yet.)

An applicative is once again a triple of things:

A polymorphic type that we know to be a functor

A definition for

`pure`

A definition for

`(<*>)`

And the definitions have to satisfy the aforementioned four laws (which you can look up for yourself).

Monads represent another step up the ladder of richness from applicative functors.

This is, of course, thanks to the bind operator.

`(>>=) :: Monad m => m a -> (a -> m b) -> m b`

We've already used this operator aplenty, but even so, we lacked the background to discuss why it matters.

Here's a piece of code that we simply can't express using only the `Functor`

or `Applicative`

machinery:

`oddEnough act = do`

v <- act

if odd v

then fail "too odd!"

else return v

Neither `fmap`

nor `<*>`

lets us "change the shape" of the outcome of a series of operations, but `>>=`

*does*.

To make that more concrete:

Any number of compositions of

`fmap`

over a*k*-element list will always give back a*k*-element list.The

`>>=`

operator lets us inspect an intermediate result and thus change what the final result will be, and do so without knowing how the`Monad`

instance is constructed.

Here's a standard function that takes a predicate expression and an action, and executes the action only if the predicate succeeds:

`when :: (Monad m) => Bool -> m () -> m ()`

when p act = if p then act else return ()

Notice that we've defined a very handy control flow function that will work in *all* monads.

Suppose we want to perform an action that returns a success/fail indication, and use that result to determine whether to perform a *second* action.

`whenM :: (Monad m) => m Bool -> m () -> m ()`

Let's write out a body for this function.

Here's a function from `Control.Monad`

that we've seen before:

`liftM :: Monad m => (a -> r) -> m a -> m r`

It bears a striking resemblance to this:

`fmap :: Functor f => (a -> b) -> f a -> f b`

And here's a function we just met:

`(<*>) :: Applicative f => f (a -> b) -> f a -> f b`

Which looks very similar to this `Control.Monad`

combinator:

`ap :: Monad m => m (a -> b) -> m a -> m b`

We've seen that `Applicative`

is defined to be a subclass of `Functor`

:

`class Functor f => Applicative f {- ... -}`

Shouldn't one of these hold, too?

`class Functor m => Monad m {- ... -}`

class Applicative m => Monad m {- ... -}

"Yes" in principle, but for historical reasons, "no".

Monads and functors were introduced to Haskell around the same time, and I'm not sure the possible relationship between them was recognized at the time.

Applicative functors arrived on the scene much later. By the time a possible resolution to the tangle was identified, there was too much code "in the wild" to change things.

Continuing our theme that just like functors and applicatives, monads are not limited to container types:

`instance Monad ((->) r) where`

-- same as the pure method of Applicative

return x = \_ -> x

f >>= g = \x -> g (f x) x

Suppose we want to parse part of a string.

We need to consume some - but probably not all - of the input, and return a result. Let's return the remainder of the input that we haven't consumed, so someone else can deal with it.

`parse :: String -> (a, String)`

Let's briefly get back to some material I didn't have time to cover a few weeks ago.

Haskell supplies a `random`

package that we can use in a purely functional setting.

`class Random a where`

random :: RandomGen g => g -> (a, g)

class RandomGen g where

next :: g -> (Int, g)

split :: g -> (g, g)

Notice the similarities between these types:

`random :: RandomGen g => g -> (a, g)`

parse :: String -> (a, String)

In each case, we emulate "state update" by returning a new state.

From that earlier lecture's unseen slides, recall that threading through all those updates is a pain:

`guess :: (RandomGen g) => (Double,g) -> (Double,g)`

guess (_,g) = (z, g'')

where z = x^2 + y^2

(x, g') = random g

(y, g'') = random g'

It would be really easy to reuse a piece of state by accident, and this is a very simple function!

Here's our most general setting for those state transformation functions:

`s -> (a,s)`

If we pay no attention to the `s`

parameter, we have one of the crucial criteria for being a `Functor`

, `Applicative`

, or `Monad`

:

- A fully polymorphic type

What about the rest?

It would actually be a bad thing if we were to declare this type to be a `Functor`

:

`s -> (a,s)`

Why? It would overlap with the `Functor`

instance for `((->) a)`

.

To avoid the potential for overlapping instances, we wrap up our state transformation type in a `newtype`

.

`newtype State s a = State {`

runState :: s -> (a,s)

}

`instance Functor (State s) where`

fmap f (State action) = State $ \origState ->

let (a, newState) = action origState

in (f a, newState)

The nice thing about our state transformer is that it works over *all* states. Some examples include:

The current state of a PRNG

The not-yet-consumed input for a parser

`instance Monad (State s) where`

return a = State $ \s -> (a, s)

State act >>= k = State $ \s ->

let (a, s') = act s

in runState (k a) s'

The bind operator simply passes the result of the first operation to the second.

We can retrieve the current state by copying it into the result field of our pair.

`get :: State s s`

get = State $ \s -> (s, s)

If we want to replace the current state with a modified version, that's equally simple.

`put :: s -> State s ()`

put s = State $ \_ -> ((), s)

Recall this function:

`guess :: (RandomGen g) => (Double,g) -> (Double,g)`

guess (_,g) = (z, g'')

where z = x^2 + y^2

(x, g') = random g

(y, g'') = random g'

`import System.Random`

import Control.Monad.State

modify' :: MonadState s m => (s -> (a,s)) -> m a

modify' f = do

s <- get

let (a,s') = f s

put s'

return a

The `MonadState`

class takes the `State`

-specific methods, and makes them available for other monads to implement:

`class (Monad m) => MonadState s m | m -> s where`

get :: m s

put :: s -> m ()

Who noticed the vertical bar and arrow?

`class (Monad m) => MonadState s m | m -> s {- ... -}`

This is called a *functional dependency*. Fundeps are used to make type checking of multi-parameter type classes tractable.

This fundep tells the type checker (and us) that the type of the state parameter `s`

can be determined from the type of the monad parameter `m`

.

How does this work?

`instance MonadState s (State s) where`

get = State $ \s -> (s, s)

put s = State $ \_ -> ((), s)

Here, we're saying that the type `State s`

is our monad, and the fundep ties its `s`

parameter to the `s`

parameter of the `MonadState`

class.

Here's a rewrite of our earlier `guess`

function to use the `modify'`

function that we just wrote:

`guess :: RandomGen g => State g Double`

guess = do

a <- modify' random

b <- modify' random

return (a*a + b*b)

Notice that we've managed to completely hide the state of the PRNG!

Suppose we were to write a simpler multi-parameter type class, without the fundep:

`class (Monad m) => MonadState s m {- ... -}`

And if we were to try to typecheck these type signatures:

`modify' :: MonadState s m => (s -> (a,s)) -> m a`

guess :: RandomGen g => State g Double

Without the fundep, the compiler would choke on these, because it has no information to assure it that the `g`

parameter to `State`

is related to the `s`

parameter to `MonadState`

.

Suppose we're running a social network, and we want to know who is connected to whom.

To build a matrix of connections, we need to represent user addresses as integer positions on each axis.

`import Control.Applicative`

import Control.Monad.State

import qualified Data.Map as Map

type Address = String

data Number = N !(Map.Map Address Int) !Int

deriving (Show)

The `Number`

type is the state we'll use (and possibly modify) while numbering.

This is the top-level address-numbering function.

`renumber :: [(Address,Address)] -> [(Int,Int)]`

renumber xs = evalState (mapM pair xs) (N Map.empty 0)

where pair (x,y) = (,) <$> number x <*> number y

This depends on a few functions we haven't seen before.

Monadic mapping:

`mapM :: Monad m => (a -> m b) -> [a] -> m [b]`

The second of the three "run me a state monad" functions:

`runState :: State s a -> s -> (a, s)`

evalState :: State s a -> s -> a

execState :: State s a -> s -> s

The super-useful `<$>`

operator is nothing but shorthand for `fmap`

.

And finally, a use in the wild for the `<*>`

operator!

This is where the real work happens.

If an address is already stored in the numbering map, our function returns the number associated with the address.

`number :: Address -> State Number Int`

number addr = do

N numMap highest <- get

case Map.lookup addr numMap of

Just j -> return j

Nothing -> do let highest' = highest + 1

newMap = Map.insert addr highest numMap

put $! N newMap highest'

return highest'

Otherwise, we increment the highest number seen, associate the previous number with the address, store the modified state, and return the number.

Reader is another widely used monad, and in fact we've already seen a form of it:

`((->) a)`

This is best understood in comparison to the state monad:

In

`State`

, every function got passed a piece of state that it could transform. This lets us achieve shared mutable state.In

`Reader`

, every function is passed a piece of state that it is not allowed to change. This lets us achieve shared*read-only*state.

As an example of a piece of immutable data that we might want to thread around all over the place, think "application configuration".

The reader monad lets us hide the plumbing of passing that information around.

The `Reader`

type is defined in `Control.Monad.Reader`

.

The *only* difference between it and `((->) a)`

is that `Reader`

is a `newtype`

wrapper around `((->) a)`

.