Module 14: Monads

This module is due Monday, December 3 at 4:00pm.

Recall that we’ve seen the (>>=) operator with the following type:

(>>=) :: Either Error a -> (a -> Either Error b) -> Either Error b

This is actually an instance of a more general pattern called a monad. A monad is a type m which supports the following operations:

Intuitively, a value of type m a represents a computation or program that computes a value of type a, and might have some “effects” (depending on m).

Let’s look at a simple example. The following Possibly type is the same as the standard Maybe, type, but redefined so you can practice making a Monad instance for it (of course, Maybe already has a Monad instance defined in the standard library).

Note that every Monad is also a Functor (which generalizes the <$> operator we saw for parsers), as well as an Applicative (which generalizes the <*> operator). (Because of time constraints, we won’t spend time talking about those but see here if you’re interested in learning more about them, or take CSCI 365, Functional Programming.) GHC can automatically generate a default instance of Functor for us (see deriving Functor above), and we can make an Applicative instance for free once we have a Monad instance: we just define pure = return and (<*>) = ap (ap is a function from the standard library which is defined in terms of return and (>>=)).

Let’s look at a simple example. First, checkEven returns Just n when its argument n is even, and Nothing otherwise. That is, it is a sort of “filter” that only “lets through” even numbers.

addEvens takes two Int values as input and adds them if both are even (and fails otherwise). Here’s a straightforward first version:

We actually don’t need the parentheses, since anonymous functions extend as far to the right as possible:

It’s annoying to have everything on the same line; it’s hard to read, and quickly gets unwieldy with larger compositions of actions. So we can introduce some newlines to make things more readable, like this:

This style became so common that it was decided to add some special syntax sugar, called do-notation, to Haskell. We can rewrite addEvens like so:

addEvens4 desugars to exactly the same thing as addEvens3.

Another monad: State

Let’s look at another example of a Monad, one we haven’t seen before. The type State s is a Monad which represents the use of a mutable state of type s. That is, a value of type State s a is a computation that results in an a and has access to a mutable state of type s.

In addition to return :: a -> State s a and (>>=) :: State s a -> (a -> State s b) -> State s b, the State monad supports two additional operations:

Let’s try some examples.

THINGS WE HAVE:

To test your implementation of tick and other exercises below, you can use the function

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

which takes a State computation to run and an initial state value, and yields the return value and final state value. For example,

ghci> runState tick 4
(4,5)

This runs the tick computation with an initial state of 4, which results in the return value 4 and an updated state of 5. (You may also be interested in evalState and execState; ask GHCi for their types to see what they do.)

Essentially, we can think of State as a mini-EDSL for expressing programs that manipulate a single mutable variable.

A tiny stack EDSL

Let’s use the State monad to build a tiny embedded DSL for operating on a mutable stack of integers.

Now let’s write a few programs using this new EDSL.

Be sure to test your programs using runStackProgI. You will find pushListI helpful for testing opI and crushI.

Error handling and monad transformers

It’s unsatisfactory having our stack language crash with error on a stack underflow. In this section we’ll explore a more principled approach to error handling via monad transformers, which allow us to combine the effects of several monads into one.

Here’s a type for runtime errors that can arise from stack programs (for now there’s only Underflow):

And now for the definition of StackProgE, which adds the possibility of errors. While we’re at it, let’s generalize from stacks of Ints to stacks of any type, represented by the type variable el. That is, something of type StackProgE el a is a computation which:

ExceptT is a monad transformer which adds the possibility of StackErrors on top of the existing monad State [el].

A deep stack EDSL

It was annoying that we had to reimplement everything when we switched from StackProgI to StackProgE. The solution is to use a deep embedding, which we can then interpret via multiple semantics. The cool thing is that we can make a Monad instance for our deep embedding, and continue to write exactly the same programs as before, using do-notation and so on. The difference is that our programs will now construct ASTs, which we can separately optimize, interpret, and so on.

Here is the AST for our deep embedding:

An alternative semantics

Now that we have a deep EDSL, we can use different semantics to interpret it without having to rewrite all our existing programs.

Consider the following definition of StackProgW, which adds WriterT [String] as compared to StackProgE. WriterT [String] adds a write-only log of type [String], which we can use to generate a sequence of log messages.

You can use the function tell :: [String] -> StackProgW el () to add some logging messages. In particular, each pop or push operation should log a message like "Popped 3" or "Pushed 6".