Providence Salumu
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:
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
:
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)
.