How to Think about Monads, starts with composition of pure functions and quickly transitioned to composition of pure functions with side-effects. If you haven't read it yet, please do. This continues where that left off.
By the end of that article, we created specialized composition functions that were equivalent to the Monadic bind.
From that article we can conclude that Monadic computations have the following properties:
- Functions are executed sequentially
- Optionally, control-flow can be short-circuited
- Optionally, Monads manage the side-effects (a.k.a maintain a context)
The only requirement of a Monad is sequential execution. But Functional Composition gives us that.
Take the following composition:
f . g . hThe order of execution is h, g and finally f. There is no way for f to execute before g and it's not possible for g to execute before h because each function is "waiting" for the output of the previous.
If you only think of Monads as sequential computers, i.e. a Monad is something that runs it's computation sequentially, then Functional Composition is sufficient to accomplish that.
But, items 2 and 3 are only supported by Monads.
Let's look at the other features that Monads can provide.
Short-circuiting is a common feature when failures happen in a Monadic computation.
Maybe is an example of a Monad that short-circuits the computation as soon as one of the operations fails, i.e. returns Nothing.
Below is the implementation for Functor, Applicative and Monad for Maybe. Notice how (>>=) doesn't call the function when the previous computation fails with a Nothing.
instance Functor Maybe where
fmap _ Nothing = Nothing
fmap f (Just x) = Just $ f x
instance Applicative Maybe where
pure = Just
Nothing <*> _ = Nothing
Just ff <*> x = fmap ff x
instance Monad Maybe where
Nothing >>= _ = Nothing -- short-circuit happens here
Just xx >>= f = f xxHere's an example of how a short-cicuit would occur in some code. Assume that tryToGetX succeeds, i.e. returns Just x and alwaysFails fails and returns Nothing.
m = do
x <- tryToGetX
y <- alwaysFail x
tryToGetZ ySince alwaysFails returns Nothing, tryToGetZ will never be called and the value m will be Nothing.
It's easier to see this when you don't use the do syntax. The following is the equivalent of the do block above
m = tryToGetX >>= (\x -> alwaysFail x >>= (\y -> tryToGetZ y)) At any point, >>= can decide to NOT call the function, which means that a Monad can short-circuit the computation at its discretion.
In this case, the second >>= doesn't call (\y -> tryToGetZ y) since the left side, x -> alwaysFail x, evaluates to Nothing.
Managing side-effects is a big part of what Monads do. Here are 2 different Monads, one whose context is a value and one whose context is a function.
The Writer Monad is one that maintains a value context, e.g. a log of operations.
To see how this is accomplished we first start with the type definition:
newtype Writer w a = Writer { runWriter :: (a, w) }Notice that (a, w) is a tuple of a computation of type a and of a log of type w. This is very similar to the side-effect functions used in How to Think about Monads.
An interesting thing to note is that runWriter has the misleading name that sounds like the name of a function. But, it's a value, i.e. the final computation and a log in a tuple.
Another thing to note about runWriter is that the signature is Writer w a -> (a, w). This is just like record accessor function singatures:
data SomeRecord =
SomeRecord {
a::Int
, b::String
}
λ> :t a
a :: SomeRecord -> IntStarting with the Functor implementation:
instance Functor (Writer w) where
fmap f (Writer (a, w)) = Writer (f a, w)fmap maps over the fst of the tuple, i.e. the computation results.
And now the Applicative:
instance Monoid w => Applicative (Writer w) where
pure a = Writer (a, mempty)
Writer (f, w) <*> Writer (a, w') = Writer (f a, w <> w')Notice that we have a type constraint on the log. It must be a Monoid. To learn about monoids, you can read Monoids in Haskell, an Introduction.
pure is implemented by wrapping a value, a, in a Writer that has an empty log, mempty.
<*> is implemented by pattern matching the Writers to get at their contents. The function, f, is then applied to the value, a and the value's log, w' is appended to the function's log w using the Monoid's append function, mappend, via the operator, <>.
This produces (f a, w <> w') which gets wrapped in a new Writer.
And finally, the Monad implementation:
instance Monoid w => Monad (Writer w) where
Writer (a, w) >>= f = let (a', w') = runWriter (f a)
in Writer (a', w <> w')Once again, w is constrained to be a Monoid.
We pattern match the Writer to get to the value, a, so we can pass it to f. Since f returns a Writer we have to use runWriter to get at the tuple, (a', w').
Once we have all of the parts, the final computation, a', and the original log, w, and the log produced by calling f a, viz. w', we can create a new Writer with the updated context.
Revisiting the side-effect functions in How to Think about Monads:
f' :: Float -> (Float, String)
f' x = (x + 10, "added 10\n")
g' :: Float -> (Float, String)
g' y = (y * 100, "multiplied 100\n")These can now be rewriten to return Writers:
f' :: Float -> Writer String Float
f' x = Writer (x + 10, "added 10\n")
g' :: Float -> Writer String Float
g' y = Writer (y * 100, "multiplied 100\n")We can compose these side-effect functions using bind, >>=:
h' :: Writer String Float
h' = g' 10 >>= f'
λ> runWriter h'
(1010, "multiplied 100\nadded 10\n")The functions f' and g' are very simple functions. But imagine a more complex function where it logs that it's going to call f' before it calls it. Then it logs that it's going to call g' and then it calls it.
v :: Float -> Writer String Float
v x =
let w1 = "calling f'\n"
Writer (y, w2) = f' x
w3 = "calling g'\n"
Writer (z, w4) = g' y
in
Writer (z, w1 <> w2 <> w3 <> w4)This code is painful since we have to manage the logging.
So we can make it easier by using >>= which will manage the logs for us:
v' :: Float -> Writer String Float
v' x =
Writer ((), "calling f'\n") >>= const (f' x) >>=
(\y -> Writer ((), "calling g'\n") >>= const (g' y))Each time the bind function is called, the logs are concatenated. So now we don't have to manage this ourselves.
But the code looks messy. Let's fix this by using do syntax:
v'' :: Float -> Writer String Float
v'' x = do
Writer ((), "calling f'\n")
y <- f' x
Writer ((), "calling g'\n")
g' yThis is a big improvement, but having to write Writer ((), "calling f'\n") is messy. We can write a helper function to minimize the noise:
tell :: Monoid w => w -> Writer w ()
tell w = Writer ((), w)Now our code looks much cleaner:
v''' :: Float -> Writer String Float
v''' x = do
tell "calling f'\n"
y <- f' x
tell "calling g'\n"
g' yIf you just saw the code for v''' you might think that context management is some kind of magic. But it's not.
By returning to the Monad implementation, we can see that context management is done on each call to bind, >>=, by returning a NEW Monad with the updated context:
instance Monoid w => Monad (Writer w) where
Writer (a, w) >>= f = let (a', w') = runWriter (f a)
in Writer (a', w <> w') -- NEW monad with updated contextWhen we code using do syntax, it's more difficult to see the bind calls. So here's v''' rewritten using >>= instead:
v'''' :: Float -> Writer String Float
v'''' x =
tell "calling f'\n" >>=
(\_ -> f' x >>=
(\y -> tell "calling g'\n" >>=
return (g' y)))Since the >>= implementation calls runWriter (f a) first and then prepends w to that result, w', the final context is built in a right-associative way:
"calling f'\n" <> ("adding 10\n" <> ("calling g'\n" <> "multiplying 100\n"))This works out nicely with <> since it's an associative binary operator by definition (see Monoids in Haskell, an Introduction).
Monads with independent side-effects will have a context that is most likely a Monoid (or at least a Semi-Group).
For Monads where the side-effect is dependent on the previous context, like in the State Monad, the bind, >>=, must make sure to pass the previous value to the function involved in the bind.
This requires the Monad to contain a function instead of a value.
The State Monad maintains a state that can be read and written to during the Monadic computation.
Here is the State defintion:
newtype State s a = State { runState :: s -> (a, s) }Unlike runWriter from the Writer Monad, runState is a function. Its signature is State s a -> s -> (a, s).
The function complicates the implementation of the State Monad when compared to Monads with values, e.g. Writer, Maybe, etc.
You may want to read Monads of Functions in Haskell if the following implementation seems confusing.
Here is the full State Monad implementation:
instance Functor (State s) where
fmap f mx = State $ \s -> let (x', s') = runState mx s in (f x', s')
instance Applicative (State s) where
pure x = State $ \s -> (x, s)
mf <*> mx = State $ \s ->
let (f, s') = runState mf s
(x, s'') = runState mx s'
in (f x, s'')
instance Monad (State s) where
mx >>= f = State $ \s -> let (x, s') = runState mx s in runState (f x) s'But first, notice how all the implementations have a similar pattern. They all start with State $ \s ->. This is how the state, s, gets passed in.
Since the Monad contains a function, all evaluations are deferred so runState is used to produce the computation and the new state. Constrast that with using pattern matching with Monads that contian values.
Since the implementations are more complicated, let's look at each part individually.
First the Functor:
instance Functor (State s) where
fmap f mx = State $ \s -> let (x', s') = runState mx s in (f x', s')runState is used to get to the results of mx. Once we have the results, we can apply f to the computation portion of the result, x'. The updated state, s' is returned as the new state.
Notice how all of this requires an initial state, s, hence the \s ->. Then it's all wrapped up in a State Monad.
Remember, that the final result is deferred until runState is called on this new State Monad with an initial state.
Next the Applicative:
instance Applicative (State s) where
pure x = State $ \s -> (x, s)
mf <*> mx = State $ \s ->
let (f, s') = runState mf s
(x, s'') = runState mx s'
in (f x, s'')pure simply creates a State Monad that wraps its parameter, x, along with the state, s, unchanged.
<*> has to evaluate both mf and mx by calling runState on each. The initial state, s, goes through the evaluation of mf first and then the resulting state is passed to the evaluation of mx resulting in the final state, s''.
The final result, f x, is the result of evaluting mf, viz. f, and applying to the result of evaluating mx, viz. x.
Once again, the final result and final state tuple are wrapped in State Monad.
Finally, the Monad:
instance Monad (State s) where
mx >>= f = State $ \s -> let (x, s') = runState mx s in runState (f x) s'runState is used twice here. The first time is to get at the result of mx and the second time is to get at the results of f x, both of which are State Monads.
The initial state is passed to the first runState call resulting in s' which is then passed to the second runState call resulting in the final state.
To fully understand the State Monad, let's write some code to use it.
First, let's write some helpers, like we did with tell, to help us access the state:
get :: State s s
get = State $ \s -> (s, s)
put :: s -> State s ()
put ns = State $ const ((), ns)These functions may seem magical at first glance. They seem to do nothing at all, but that's not true.
get takes the state that's passed in to the State Monad's function and "leaks" it to the computation.
put takes it's state parameter, ns, and simply makes that the resulting state ignoring the state that's normally passed in to the State Monad's function.
Assuming the state is of type Int, get and put can be used as follows:
do
s <- get
put $ s + 1It would be nicer to have a single line like:
do
modify (+ 1)So let's write modify:
modify :: (s -> s) -> State s ()
modify f = get >>= (put . f)Here we first get the state and pass it to f for modification and then finally to put.
Now let's use these in a real implementation:
data Statistics =
Statistics {
evenCount :: Int,
oddCount :: Int
} deriving Show
initialStats :: Statistics
initialStats = Statistics 0 0
isEven :: Int -> Bool
isEven = (== 0) . (`mod` 2)
isOdd :: Int -> Bool
isOdd = not . isEven
modifyStats :: Int -> State Statistics ()
modifyStats n =
modify $ \s -> Statistics {
evenCount = if isEven n then evenCount s + 1 else evenCount s
, oddCount = if isOdd n then oddCount s + 1 else oddCount s
}
fs :: Int -> State Statistics Int
fs n = do
modifyStats n
return $ n + 10
gs :: Int -> State Statistics Int
gs n = do
modifyStats n
return $ n * 100When this is run, it produces:
λ> runState (fs 1 >>= gs) initialStats
(1100,Statistics {evenCount = 0, oddCount = 2})Since do syntax can hide a lot of details, here's fs and gs using >>=:
fs' :: Int -> State Statistics Int
fs' n = modifyStats n >>= const (return $ n + 10)
gs' :: Int -> State Statistics Int
gs' n = modifyStats n >>= const (return $ n * 100)Since modifyStats returns a result of (), we throw it out with const.
Or we can use >> which throws away the results for us:
fs'' :: Int -> State Statistics Int
fs'' n = modifyStats n >> return (n + 10)
gs'' :: Int -> State Statistics Int
gs'' n = modifyStats n >> return (n * 100)Unlike the Writer Monad, the State Monad's state management is left-associative. To illustrate this, let's write an inefficient version of fs that uses get, put and >>=:
fs''' :: Int -> State Statistics Int
fs''' n =
get >>=
(\s ->
put Statistics {
evenCount = if isEven n then evenCount s + 1 else evenCount s
, oddCount = if isOdd n then oddCount s + 1 else oddCount s
} >>=
(\_ -> return $ n + 10))Looking again at the Monad implementation:
instance Monad (State s) where
mx >>= f = State $ \s -> let (x, s') = runState mx s in runState (f x) s'Since the >>= implementation calls runState mx s first (left-side of >>=) and then runState (f x) (right-side of >>=), the final context is built in a left-associative way:
((get's state --> put's state) --> (\_ -> return $ n + 10))First, get will produce a state that will be passed to put which will produce a state that will be passed to (\_ -> return $ n + 10)).
Each function in the computation is dependent on the previous computation as far as state is concerned. This is in sharp contrast to the Writer Monad where each function was independent of the previous computation.
Hopefully, implementing Maybe, Writer and State monads and understanding how they accomplish Flow Control and Side-effects has removed some of the mystery of Monads.
What's interesting is that all the implementations are very simple, but provide great power and flexibility. And when coupled with some Monadic helper functions, i.e functions of the form a -> m b, the Monad gains it's own API.