0106: Email Tutorials ‐ Monads III

AFP 9 – Monads III – Graham Hutton

📚 Table of Contents

1. Email 600 – Where We Are in the Monad Journey
2. Email 601 – Refresher: The Monad Class
3. Email 602 – Refresher: What the State Monad Models
4. Email 603 – State Transformers Revisited
5. Email 604 – Revealed vs Hidden Information
6. Email 605 – Two Function Types Compared
7. Email 606 – The “Under the Waterline” Model
8. Email 607 – return for the State Monad (Revisited)
9. Email 608 – bind for the State Monad (Revisited)
10. Email 609 – Why Bind Hides State Plumbing
11. Email 610 – The Tree Relabeling Problem
12. Email 611 – Defining a Tree Type
13. Email 612 – What “Relabeling” Means
14. Email 613 – Manual State Threading (The Hard Way)
15. Email 614 – Why Manual State Threading Is Error-Prone
16. Email 615 – Recognizing a State Transformer
17. Email 616 – Fixing the State Type
18. Email 617 – A Fresh Label Generator
19. Email 618 – Relabeling Trees with the State Monad
20. Email 619 – Why the Monadic Version Is Better
21. Email 620 – Extracting a Pure Interface
22. Email 621 – What We Have Learned
23. Glossary
24. Quiz Questions (Table Format)
25. Quiz Options (Table Format)
26. Next Steps

Email 600 – Where We Are in the Monad Journey

So far in our monad journey, we have completed two major steps. First, we rediscovered the idea of monads by studying concrete examples. Second, we learned the formal definition of monads in Haskell.

We have already seen three important monads:

• The Maybe monad, which models failure.
• The List monad, which models nondeterminism.
• The State monad, which models computations that manipulate state.

In this lecture, we return to the State monad, not to redefine it, but to use it in practice.

Email 601 – Refresher: The Monad Class

The Haskell definition of a monad fits on a single slide:

class Applicative m => Monad m where
  (>>=)  :: m a -> (a -> m b) -> m b
  return :: a -> m a

This definition tells us two important things.

First, every monad must already be an applicative. Second, a monad provides a generic sequencing operator, called bind.

Email 602 – Refresher: What the State Monad Models

The State monad models computations that carry and modify state, while remaining purely functional.

A state is simply some value that may change over time, such as a counter or a label generator.

Crucially, no mutation is used. Instead, state is passed explicitly—though usually hidden from us.

Email 603 – State Transformers Revisited

A state transformer takes an input state and produces:

1. A result value
2. A possibly modified state

This is captured by the type:

State -> (a, State)

To turn this into a monad, we wrap it using a newtype:

newtype ST a = S (State -> (a, State))

This allows us to define Functor, Applicative, and Monad instances.

Email 604 – Revealed vs Hidden Information

One of the most important ideas in this lecture is the distinction between:

• What the programmer sees
• What the monad manages behind the scenes

The State monad hides state manipulation, allowing us to focus only on the meaningful data flowing through the computation.

Email 605 – Two Function Types Compared

Consider these two function types:

Char -> Int
Char -> ST Int

The first is a pure function. It takes a character and returns an integer.

The second looks similar, but it hides something important.

Email 606 – The “Under the Waterline” Model

A function of type:

Char -> ST Int

is not just mapping characters to integers.

Under the hood, it is equivalent to:

Char -> State -> (Int, State)

The state flows underneath, hidden from view. This leads to a powerful mental model:

Values flow above the waterline. State flows below the waterline.

The programmer sees the values. The monad handles the state.

Email 607 – return for the State Monad (Revisited)

The return function lifts a value into the State monad:

return x = S (\s -> (x, s))

This means:

• The value x is returned unchanged.
• The state is passed through unchanged.

Above the waterline, the value flows straight through. Below the waterline, the state remains untouched.

Email 608 – bind for the State Monad (Revisited)

The bind operator sequences two stateful computations:

st >>= f =
  S (\s ->
    let (x, s') = app st s
    in app (f x) s'
  )

What happens here is simple but powerful:

1. Run the first computation on the state.
2. Extract its result and updated state.
3. Feed the result into the next computation.
4. Continue with the updated state.

All state threading happens below the waterline.

Email 609 – Why Bind Hides State Plumbing

When using >>=, the programmer does not manually pass state around.

The state flows automatically from one computation to the next. This eliminates boilerplate and prevents subtle bugs.

Email 610 – The Tree Relabeling Problem

We now turn to a concrete example: relabeling trees.

The goal is simple:

Replace every leaf value in a tree with a fresh, unique integer.

Email 611 – Defining a Tree Type

We use a simple binary tree with values in the leaves:

data Tree a
  = Leaf a
  | Node (Tree a) (Tree a)

This structure is recursive and ideal for demonstrating stateful traversal.

Email 612 – What “Relabeling” Means

Given a tree with values like A, B, and C, we want to produce:

• A tree of integers
• Each integer is unique
• Labels increase as we traverse the tree

Email 613 – Manual State Threading (The Hard Way)

Without monads, we must write a function like:

Tree a -> Int -> (Tree Int, Int)

This function must:

• Accept the next fresh label
• Return the relabeled tree
• Return the next unused label

Every recursive call must pass labels carefully.

Email 614 – Why Manual State Threading Is Error-Prone

Manual state threading leads to:

• Complicated plumbing code
• Hard-to-read definitions
• Easy mistakes (such as reusing labels)

Even a single wrong variable can break correctness.

Email 615 – Recognizing a State Transformer

The key insight is this:

The manual relabeling function already is a state transformer.

Once we recognize this, the solution becomes obvious: use the State monad.

Email 616 – Fixing the State Type

We now make the state concrete:

type State = Int

The state represents the next fresh label.

Email 617 – A Fresh Label Generator

We define a helper state transformer:

fresh :: ST Int
fresh = S (\n -> (n, n + 1))

This returns the current label and increments the state.

Above the waterline: we get a number. Below the waterline: the counter advances.

Email 618 – Relabeling Trees with the State Monad

Now the relabeling function becomes beautifully simple:

mLabel :: Tree a -> ST (Tree Int)
mLabel (Leaf _) = do
  n <- fresh
  return (Leaf n)

mLabel (Node l r) = do
  l' <- mLabel l
  r' <- mLabel r
  return (Node l' r')

There is no explicit state plumbing.

Email 619 – Why the Monadic Version Is Better

This version is:

• Shorter
• Safer
• Easier to understand
• Structurally identical to the problem description

The State monad handles the hard parts for us.

Email 620 – Extracting a Pure Interface

To expose a clean API, we define:

label :: Tree a -> Tree Int
label t = fst (app (mLabel t) 0)

This is a pure function, with no visible state.

Email 621 – What We Have Learned

The State monad allows us to:

• Write imperative-style logic
• Without mutation
• With explicit sequencing
• While keeping pure function types

This is why it is one of the most important monads in functional programming.

🧾 Glossary

State monad – models stateful computations in a pure way State transformer – State -> (a, State) Fresh value – a value guaranteed to be unique Bind (>>=) – sequences computations while hiding state Above the waterline – visible values Below the waterline – hidden state plumbing

📖 Recommended Reading

Buy Book

🎓 Final Step: Quiz & Progress Badge

Start Quiz (Haskell 18 – Functor)