Each worksheet prints cleanly on A4 or Letter. Answer keys are on a separate page.

The Lumenary · First-year graduate

Monads

Name: ______________________

Date: ______________________

You will learn to

Verify the monad laws for the list, power-set and maybe monads on $\cat{Set}$ , and identify their algebras (monoids, complete join-semilattices, pointed sets)
Prove that every adjunction $F \dashv G$ induces a monad $GF$ , and construct the Kleisli and Eilenberg–Moore adjunctions that recover any monad
Construct the comparison functors and show that the Kleisli and Eilenberg–Moore categories need not be equivalent
State Beck's monadicity theorem, show that $\cat{Grp}$ is monadic over $\cat{Set}$ and $\cat{Top}$ is not
Explain how monads model computational effects and probabilistic transitions

1.
The maybe monad on $\mathbf{Set}$ has $TX = X \sqcup \{\bot\}$ , $\eta_X(x) = x$ , and $\mu_X$ collapsing the two copies of $\bot$ . What is a $T$ -algebra $(A, a)$ ?
- A.A set $A$ with a chosen element $a(\bot) \in A$ (a pointed set)
- B.A monoid
- C.A set with an idempotent map $e : A \to A$
- D.Any set, with no extra structure
2.
How many algebra structures $a : \mathcal{P}A \to A$ for the power-set monad are there on the three-element set $A = \{p, q, r\}$ ?
3.
In the Kleisli category of the list monad, let $f(n) = [n, n + 1]$ and $g(n) = [10n]$ (both from $\mathbb{Z}$ to $\mathrm{List}(\mathbb{Z})$ ). What is $(g \circ_T f)(1) = \mu(Tg(f(1)))$ ?
- A. $[10, 20]$
- B. $[[10], [20]]$
- C. $[10, 11]$
- D. $[10]$
4.
Let $F \dashv G$ with $F : \mathcal{C} \to \mathcal{D}$ , unit $\eta$ and counit $\varepsilon$ . The induced monad is $T = GF$ on $\mathcal{C}$ . What is its multiplication $\mu_X : GFGFX \to GFX$ ?
- A. $G(\varepsilon_{FX})$
- B. $\eta_{GFX}$
- C. $F(\eta_{GX})$
- D. $\varepsilon_{FGFX}$
5.
In proving that $\eta_A$ is a right identity in the Kleisli category, we write, for $f : A \to TB$ ,

$f \circ_T \eta_A = \mu_B \circ Tf \circ \eta_A = \mu_B \circ \eta_{TB} \circ f = f.$

Which two facts justify the second and third equalities, in order?
- A.Naturality of $\eta$ ; then the left unit law $\mu \circ \eta T = \mathrm{id}$
- B.The right unit law $\mu \circ T\eta = \mathrm{id}$ ; then associativity
- C.Naturality of $\mu$ ; then naturality of $\eta$
- D.The two triangle identities of an adjunction
6.
For the list monad $T$ on $\mathbf{Set}$ , $\mathbf{Set}^T \simeq \mathbf{Mon}$ . Which argument shows that the Kleisli category $\mathbf{Set}_T$ is not equivalent to $\mathbf{Mon}$ ?
- A. $\mathbb{Z}/2$ has exactly two monoid endomorphisms, but every object of $\mathbf{Set}_T$ has either one or infinitely many endomorphisms.
- B. $\mathbf{Mon}$ has more objects than $\mathbf{Set}_T$ .
- C. $\mathbf{Mon}$ has a zero object and $\mathbf{Set}_T$ does not.
- D.The comparison functor $\mathbf{Set}_T \to \mathbf{Set}^T$ is not full.
7.
Which forgetful functors to $\mathbf{Set}$ are monadic? (Choose all that apply.)
- A. $\mathbf{Grp} \to \mathbf{Set}$
- B. $\mathbf{Ring} \to \mathbf{Set}$
- C.Compact Hausdorff spaces $\to \mathbf{Set}$
- D. $\mathbf{Top} \to \mathbf{Set}$
- E.Posets $\to \mathbf{Set}$
8.
In the Lean file, a list algebra on X has act : List X → X. Which field states the associativity law $a \circ Ta = a \circ \mu_A$ ?
- A.∀ xss : List (List X), act (xss.map act) = act xss.flatten
- B.∀ x : X, act [x] = x
- C.∀ x y : X, act [x, y] = act [y, x]
- D.∀ xss : List (List X), act xss = act xss.flatten
9.
Write kleisli(f, g) returning the Kleisli composite (first f, then g) for the list monad: f and g are Python functions returning lists, and the composite applies g to every output of f and concatenates. Also write unit(x) returning [x]. The tests check the Kleisli category laws on examples.
Computational — Practice

Answer key — Monads

1.
The unit law says $a(x) = x$ for every $x \in A$ , so $a$ is determined by the single value $a(\bot) \in A$ . Checking the associativity law on the three kinds of element of $TTA$ ( $\bot$ , the inner $\bot$ , and $x$ ) shows it always holds. So an algebra is exactly a pointed set, and algebra morphisms are base-point-preserving maps: $\mathbf{Set}^T$ is the category of pointed sets.
2.
A $\mathcal{P}$ -algebra is the same as a complete join-semilattice, via $x \le y \iff a\{x, y\} = y$ and $a(S) = \bigvee S$ . A three-element complete lattice has a bottom and a top, and the remaining element lies strictly between them: it is a chain. Chains on $\{p, q, r\}$ correspond to orderings of the three letters, so there are $3! = 6$ algebras. The experiment monads_algebra_count confirms this by searching all $3^5 = 243$ maps satisfying the unit law.
3.
$f(1) = [1, 2]$ ; $Tg$ applies $g$ entrywise, giving $[[10], [20]]$ ; $\mu$ concatenates, giving $[10, 20]$ . In general the Kleisli composite of many-valued functions collects every output of $g$ over every output of $f$ .
4.
The counit $\varepsilon : FG \Rightarrow \mathrm{id}_{\mathcal{D}}$ removes an adjacent $FG$ . Whiskering, $G\varepsilon F$ has components $G(\varepsilon_{FX}) : G(FG)FX \to GFX$ . The triangle identities then give the unit laws and naturality of $\varepsilon$ gives associativity (Theorem 1).
5.
Second equality: naturality of $\eta$ applied to $f : A \to TB$ , namely $Tf \circ \eta_A = \eta_{TB} \circ f$ . Third equality: the left unit law $\mu_B \circ \eta_{TB} = \mathrm{id}_{TB}$ . (The other identity law, $\eta_B \circ_T f = f$ , uses the right unit law instead.)
6.
If $E : \mathbf{Mon} \to \mathbf{Set}_T$ were an equivalence, then $\mathrm{End}(\mathbb{Z}/2) \cong \mathrm{End}(E(\mathbb{Z}/2))$ . The left side has exactly two elements ( $1 \mapsto 0$ , $1 \mapsto 1$ ). The right side is the set of functions $A \to \mathrm{List}(A)$ for some set $A$ : one function if $A = \varnothing$ , infinitely many otherwise. Contradiction. (Contrast the maybe monad, where every algebra is free and the two categories are equivalent.)
7.
Groups, rings and compact Hausdorff spaces are monadic over $\mathbf{Set}$ (the first two are varieties; the third is Manes' theorem for the ultrafilter monad). For topological spaces and posets the left adjoint is the discrete structure, the induced monad is the identity, and its algebras are plain sets; the comparison functor is the forgetful functor itself, which is not an equivalence because it does not reflect isomorphisms.
8.
The associativity law compares evaluating the inner lists first, act (xss.map act), with flattening first, act xss.flatten. This is the field ListAlgebra.assoc in Lumenary.Monads.
9.
```
def unit(x):
    return [x]


def kleisli(f, g):
    return lambda a: [c for b in f(a) for c in g(b)]
```
The comprehension is $\mu \circ Tg \circ f$ : for b in f(a) runs over the outputs of $f$ , g(b) is $Tg$ applied entrywise, and the nested loop flattens. The tests check the identity and associativity laws on examples; the lesson (and the Lean theorem list_kleisli_laws) proves them in general.