Monads and interaction, MGS 2021
Exercise class 3
1. Remember yesterday we compared extensional and intensional variants
of state monads:
St X = S => S x X vs St_i X = mu Z. X + (S => Z) + (S x Z)
St_i X \cong^mu X + (S => St_i X) + (S x St_i X)
We defined monad maps in both directions (to describe how you convert
between the notions of computation these monads model) and also an
on-the-fly "normalizer" for St_i.
Carry out the same project for these monads of nondeterminism:
ND X = NEList X vs ND_i X = mu Z. X + Z x Z
= mu Z. X x (1 + Z)
It helps to keep in mind that algebras of T_i are the same as
semigroups.
2. Describe the Kleisli category of the reader monad for S. Describe
the coKleisli category of the coreader comonad for S:
Rd^S X = S => X
Cord^S Y = S x Y
What can you observe?
3. Find out what coalgebras of the cowriter comonad for (P, o, pl)
amount to.
Cowr^P Y = P => Y
4. Here are two variants of the costate comonad:
Cost Y = S x (S => Y) vs Cost_i Y = nu W. Y x (S x W) x (S => αΊ‚)
Cost_i Y =^nu Y x (S x Cost_i Y) x (S => Cost_i Y)
Write comonad maps corresponding to conversions between these two
notions of environment.
(This is trickier.) Can you write an on-the-fly normalizer for Cost_i?
(What does it even have to do??)