0104 : Email Tutorials – Monads I: Basic Concepts (Full Tutorial)

AFP 5 — Monads I

📚 Table of Contents

1. Email 700 – Where We Are: From Functors to Applicatives
2. Email 701 – Programming with Effects Revisited
3. Email 702 – A Simple Expression Language
4. Email 703 – A Naive Evaluator (and Its Problem)
5. Email 704 – Introducing Failure with Maybe
6. Email 705 – A Safe Division Operator
7. Email 706 – An Explicitly Safe Evaluator
8. Email 707 – Why the Explicit Version Is Unsatisfactory
9. Email 708 – Observing a Repeated Pattern
10. Email 709 – Abstracting the Pattern: The Bind Operator
11. Email 710 – The Type of Bind
12. Email 711 – Rewriting the Evaluator Using Bind
13. Email 712 – Understanding Bind as Sequencing
14. Email 713 – The General Bind Pattern
15. Email 714 – do Notation: Cleaning Up the Syntax
16. Email 715 – The Final Evaluator Using do Notation
17. Email 716 – Why This Is Still Pure Functional Programming
18. Email 717 – What We Have Really Discovered
19. Glossary
20. Quiz Questions (Table Format)
21. Quiz Options (Table Format)
22. Next Steps

Email 700 – Where We Are: From Functors to Applicatives

Over the last few lectures, we have gradually built up a hierarchy of abstraction for programming with effects.

We started with functors, which let us map a function over values inside a data structure. Then we moved to applicative functors, which let us apply pure functions to effectful arguments.

At this point, we know how to write expressions such as:

pure (+) <*> Just 1 <*> Just 2

This applies a pure function to arguments that may fail, and the applicative machinery handles the effects for us.

However, applicatives still have a limitation: they assume that the structure of the computation is fixed in advance.

Email 701 – Programming with Effects Revisited

The core question of this lecture is:

What if later computations depend on the results of earlier ones?

Applicatives cannot express this kind of dependency, because all arguments must already be present. To solve this problem, we need a new abstraction—one that allows sequencing, where the next step can depend on the value produced by the previous step.

Rather than defining this abstraction immediately, we will rediscover it through a concrete example.

Email 702 – A Simple Expression Language

We begin by defining a very small expression language.

data Expr
  = Val Int
  | Div Expr Expr

An expression is either:

• a literal integer value, or
• the division of one expression by another.

For example:

e = Div (Val 6) (Val 3)

represents the arithmetic expression 6 / 3.

Email 703 – A Naive Evaluator (and Its Problem)

We now write a simple evaluator for expressions.

eval :: Expr -> Int
eval (Val n)     = n
eval (Div x y)   = eval x `div` eval y

This definition is elegant and concise. Unfortunately, it has a serious flaw: division by zero.

If eval y evaluates to 0, the program crashes. In real programs, crashing is unacceptable—we want to handle errors safely.

Email 704 – Introducing Failure with Maybe

We already know a type that captures the idea of failure: Maybe.

The type Maybe a represents a computation that may either:

• succeed with a value Just a, or
• fail with Nothing.

To handle division by zero safely, we will refine our evaluator so that it returns a Maybe Int instead of an Int.

Email 705 – A Safe Division Operator

First, we define a safe version of integer division:

safeDiv :: Int -> Int -> Maybe Int
safeDiv _ 0 = Nothing
safeDiv n m = Just (n `div` m)

This function never crashes. Instead, it explicitly represents failure using Nothing.

Email 706 – An Explicitly Safe Evaluator

We now rewrite the evaluator using Maybe.

eval :: Expr -> Maybe Int
eval (Val n) = Just n
eval (Div x y) =
  case eval x of
    Nothing -> Nothing
    Just n  ->
      case eval y of
        Nothing -> Nothing
        Just m  ->
          safeDiv n m

This evaluator is correct and safe. It never crashes.

Email 707 – Why the Explicit Version Is Unsatisfactory

Although correct, this version has several problems:

1. It is verbose and repetitive.
2. Failure propagation is handled manually.
3. The core idea of the computation is obscured by error-handling code.

Conceptually, the evaluator still does something very simple:

Evaluate x, evaluate y, and then divide the results.

But this simplicity is hidden by layers of case analysis.

Email 708 – Observing a Repeated Pattern

If we look carefully at the code, we see the same pattern appearing again and again:

case mx of
  Nothing -> Nothing
  Just x  -> f x

This pattern says:

• If a computation fails, propagate the failure.
• If it succeeds, pass the result to the next computation.

This pattern occurs every time we sequence two Maybe computations.

Email 709 – Abstracting the Pattern: The Bind Operator

Since this pattern appears so frequently, we should abstract it out into a single operator.

We define an operator—commonly called bind:

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing >>= _ = Nothing
Just x  >>= f = f x

This operator captures exactly the repeated pattern we observed.

Email 710 – The Type of Bind

The type of bind tells us a lot:

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b

Interpretation:

• Take a computation that may fail.
• If it succeeds, pass its result to a function that returns another computation.
• If it fails, propagate the failure automatically.

Bind gives us sequencing with failure propagation.

Email 711 – Rewriting the Evaluator Using Bind

Using bind, we can dramatically simplify the evaluator.

eval :: Expr -> Maybe Int
eval (Val n) = Just n
eval (Div x y) =
  eval x >>= \n ->
  eval y >>= \m ->
  safeDiv n m

This definition is concise, readable, and directly expresses the intent of the computation.

Email 712 – Understanding Bind as Sequencing

The bind operator lets us write code that reads procedurally:

1. Evaluate x.
2. If successful, evaluate y.
3. If successful, divide the results safely.

At no point do we manually check for failure. That logic is handled entirely by (>>=).

Email 713 – The General Bind Pattern

The general pattern of bind-based programming looks like this:

m1 >>= \x1 ->
m2 >>= \x2 ->
...
mn >>= \xn ->
f x1 x2 ... xn

This sequence succeeds only if every step succeeds. If any step fails, the entire computation fails automatically.

Email 714 – do Notation: Cleaning Up the Syntax

Because this pattern is so common, Haskell provides special syntax called do notation.

The previous code can be rewritten as:

do
  x1 <- m1
  x2 <- m2
  ...
  f x1 x2

This notation hides the lambdas and bind operators, making the code easier to read.

Email 715 – The Final Evaluator Using do Notation

Using do notation, the evaluator becomes:

eval :: Expr -> Maybe Int
eval (Val n) = Just n
eval (Div x y) = do
  n <- eval x
  m <- eval y
  safeDiv n m

This code closely mirrors the original unsafe evaluator, but it is now completely safe.

Email 716 – Why This Is Still Pure Functional Programming

Although the code looks imperative, it is still:

• pure,
• declarative,
• referentially transparent.

There is no mutation, no hidden state, and no exceptions. Effects are represented explicitly in the type system.

Email 717 – What We Have Really Discovered

We have not yet formally defined monads—but we have effectively rediscovered them.

A monad is precisely a structure that supports:

• embedding values (return / pure),
• sequencing computations with dependency (>>=).

In the next lecture, we will formalize this idea and define the Monad typeclass.

🧾 Glossary

Effect – extra computational behavior such as failure, state, or nondeterminism. Bind (>>=) – sequences computations while managing effects automatically. Maybe monad – models computations that may fail. Sequencing – executing computations one after another, where later steps depend on earlier results. do notation – syntactic sugar for chains of bind operations.

📖 Recommended Reading

Buy Book

🎓 Final Step: Quiz & Progress Badge

Start Quiz (Haskell 18 – Functor)