We're all pretty familiar with Monads that contain values, e.g. Maybe a and Either e a. Typically, these are value type, e.g. Maybe String, Maybe Int, Either String Int, Either MyError MyResult.
When fmap is called on a Maybe Int, it is clear that the Int is going to be mapped to its new value when the fmap is evaluated, e.g.:
fmap (* 10) Just 1 === Just 10But it's a real mind twist when the Monad contains a function. How does fmap work? It can only return a new function which means that its evaluated at some later date. That single fact is not always clear to the beginner (it wasn't to me which is why I'm writing this).
Turns out that there are some really useful Monads that contain functions, e.g. Reader, Writer and State. Before delving into those Monads with all of the their implied use cases, it may be helpful to just think of a simple case of a Monad with a function that needs to get evaluated to produce a final result.
Hopefully, after doing so, those other Monads will be easier to understand.
Let's create a Monad that evaluates a computation with a single value as its input.
newtype Eval v r = Eval { eval :: v -> (r, v) }Here v is the type of value passed into the evaluator and r is the result. Notice that, unlike Maybe, this type contains a function v -> (r, v).
Once we evaluate the function, we will get a tuple which has the result of the evaluation r and the value v that was used to produce that result.
By the way, Maybe can take a function, but it's NOT designed to only take functions. And hence, the implementation of Maybe is not conducive to working with functions.
Our implementation of Eval is going to make dealing with the function easier. We are already seeing this with the accessor function eval.
One nice thing about the Monad lineage is that Functor and Applicative can be generalized in terms of bind (>>=). Control.Monad allows us to do this.
We also must fix the v type so that our type only has one parameter which Functor, Applicative and Monad all expect (kind * -> *). This is why we define the following instances with Eval v (kind * -> *) instead of Eval (kind * -> * -> *).
import qualified Control.Monad as CM
instance Functor (Eval v) where
fmap = CM.liftM
instance Applicative (Eval v) where
pure = return
(<*>) = CM.apBoth liftM and ap rely on Eval v being a Monad. So at this point, the compiler will complain. It will also complain since we are setting pure equal to return which is a Monad function.
Here's where the real work gets done.
Let's start with return:
return r = Eval $ \v -> (r, v)When we use return, the value of v is unchanged which works perfectly for our requirements.
Before we move on to >>=, we should examine the implementation of return further. Notice how we pass a function to the data constructor. We're going to need to do that in >>= but not by using return for the aforementioned reasons.
Bind is a bit tricky. Let's first look at the definition of >>= to try to discern a reasonable strategy for implementing bind.
(>>=) :: Eval v a -> (a -> Eval v b) -> Eval v b
e >>= f = ...Internally, we're going to have to crack open e so we can apply f to it. That can be done using the eval accessor.
Notice that f wraps up the result in an Eval so after that it seems we are done.
Let's give that a try:
-- DOES NOT COMPILE !!!!
e >>= f = f $ fst $ eval e vWell, that's not going to work, because where does the v come from? We need to wrap this in the same way we did with return.
Let's try again:
-- DOES NOT COMPILE
e >>= f = Eval $ \v -> f $ fst $ eval e vThis time we account for v but our lambda returns an Eval v not (r, v). The way we fix that is by using eval again:
e >>= f = Eval $ \v -> eval (f $ fst $ eval e v) vThe need to use eval twice is a common implementation pattern in Monads with functions because of the type of f, i.e. a -> m b. If it were simply, a -> b then this extra step would not be necessary but then the function wouldn't be >>=. It would be fmap.
So now here is our final instance definition:
instance Monad (Eval v) where
return r = Eval $ \v -> (r, v)
e >>= f = Eval $ \v -> eval (f $ fst $ eval e v) vOne other thing to note here is that throughout all of the computations, v is unchanged. That's only because of the behavioral requirements we initially defined for our Monad.
If this requirement was lifted, a very different implementation would have been needed for >>=:
instance Monad (Eval v) where
return r = Eval $ \v -> (r, v)
-- UNNECESSARILY COMPLEX FOR OUR REQUIREMENTS
e >>= f = Eval $ \v0 ->
let (r1, v1) = eval e v0
in eval (f r1) v1In this unnecessarily complex implementation, we distinguish the different vs in v0 and v1 which is returned from the first eval.
Turns out that this type of implementation is a necessary for the State monad.
Here is the full implementation, so far:
newtype Eval v r = Eval { eval :: v -> (r, v) }
instance Functor (Eval v) where
fmap = CM.liftM
instance Applicative (Eval v) where
pure = return
(<*>) = CM.ap
instance Monad (Eval v) where
return r = Eval $ \v -> (r, v)
e >>= f = Eval $ \v -> eval (f $ fst $ eval e v) vTo use this in a program, we need a few helpers.
First, we need a constructor, which we will call createEval:
createEval :: (v -> r) -> Eval v r
createEval f = Eval $ \v -> (f v, v)Here f is the initial function to be evaluated with different values of v.
Next, we need a helper to just do the evaluation and return the result, which we will call evaluate:
evaluate :: Eval v r -> v -> r
evaluate e v = fst $ eval e vLet's define a test Evaluator:
test :: Eval Integer Integer
test = (* 3) <$> createEval (* 10)We first create an evaluator that takes its value and multiplies it by ten, createEval (* 10).
Next we map a multiply by 3 on it. (Remember that <$> is the infix of fmap.)
Now we can our Eval monad:
evaluate test 10 === 300
evaluate test 1 === 30
eval test 10 === (300, 10)
eval test 1 === (30, 1)Notice, as stated at the beginning, that the effect of the fmap doesn't happen until we call eval, either directly or indirectly via evaluate.
This is very different from an fmap on [a] or Maybe a. Granted Haskell is lazy and will only evaluate fmap when the result is needed.
But with Monads of functions, an extra operation is your responsibility. You need to call (and someone needs to write) a function to do a final evaluation. All the operations before this step were just building an array or tree of functions that, when called, will produce the desired final result.
In Reader, it's called runReader. In State, it's called runState.
So it's really a mindset change from our run of the mill Monads. We have to keep in mind that we are creating a Deferred computation that we are responsible for performing.
I hope that this will help when you learn about State, Reader, Writer and their brethren.