# Algebras of the environment monad

What are the algebras of the environment monad $-^E$ in $\mathbf{Set}$?

Abstractly, I see that an algebra of $-^E$ is a set $X$ with an operation $f : X^E \to X$ that obeys two laws: an "idempotence law", $f(x, x, …) = x$, and a "diagonal law" $$f(f(x^1_1, x^1_2, …), f(x^2_1, x^2_2, …), …) = f(x^1_1, x^2_2, …)$$ The free algebra is $X = Y^E$ with the diagonal function $f : Y^{E \times E} \to Y^E$. For any $X$, the $i$th projection is another example. That's all I've got so far.

Is there a more natural way to describe these things?

Edit. The environment monad ("Reader" for functional programmers) consists of the functor $A \mapsto A^E$, with the unit $\eta_A : A \to A^E$ given by constant functions, i.e. currying the projection $\pi_1 : A \times E \to A$, and the join $\mu_A : A^{E \times E} \to A^E$ given by composition with the diagonal function $\Delta : E \to E \times E$.

Also, I see now how to generalize my two examples a bit. Let $X = Y^A$ for some set $A$, and say $g : A \to A \times E$ commutes with the projection and diagonal: $$\pi_1 \circ g = 1_A$$ $$(1_A \times \Delta) \circ g = (g \times 1_E) \circ g$$ (Sorry, I don't know how to make diagrams here.) Then we can define $f : Y^{A \times E} \to Y^A$ by composition with $g$. The two examples I gave before are the special cases where $g = \Delta$ or $g : 1 \to 1 \times E$ picks out an element of $E$.

• It would be helpful for this question to contain a definition of the environment monad, to make it more self-contained. – Qiaochu Yuan Jul 15 '14 at 19:02
• @QiaochuYuan I infer from the description that the environment monad is the monad induced by the unique comonoid structure on $E$ (wrt the cartesian monoidal structure). – Zhen Lin Jul 15 '14 at 19:03
• Thanks for the comment. I've added more detail to the question. – Jeff Russell Jul 15 '14 at 19:34

## 2 Answers

The best way of understanding the algebras for a monad is to find an adjunction whose induced monad is (isomorphic to) the one you started with. In this case, one may verify that the adjunction $$E^* \dashv \Pi_E : \mathbf{Set}_{/ E} \to \mathbf{Set}$$ has induced monad (isomorphic to) the "environment" monad $(-)^E$. Unfortunately, this adjunction is not monadic in general – indeed, the dependent product functor $\Pi_E : \mathbf{Set}_{/ E} \to \mathbf{Set}$ is not always faithful. Nonetheless, this suggests that algebras for $(-)^E$ should have something to do with "sets over $E$", or more plainly, $E$-indexed families of sets.

Let $X$ be an $E$-indexed family of sets. Then $\Pi_E X = \prod_{e \in E} X_e$, and this has a canonical $(-)^E$-algebra structure, namely $(\Pi_E X)^E \to \Pi_E X$ defined by $s \mapsto (e \mapsto s (e) (e))$. (Note that if $s \in (\Pi_E X)^E$, then $s (e) \in \Pi_E X$, so it makes sense to write $s (e) (e)$, and it is an element of $X_e$ as required.) Thus we might say that an $(-)^E$-algebra is a generalised function on $E$ – so generalised that we can't actually evaluate it!

Well, we can still try. Suppose $A$ is an $(-)^E$-algebra, say with action $\alpha : A^E \to A$. Define an $E$-indexed family of sets $X$ as follows: $X_e$ is the quotient of $A$ by the smallest equivalence relation that identifies $\alpha (f)$ and $f (e)$ for every $f \in A^E$. This $X$ has the following universal property: for any $E$-indexed family of sets $Y$, there is a natural bijection between $E$-indexed maps $X \to Y$ and $(-)^E$-algebra homomorphisms $A \to \Pi_E Y$. In particular, there is a canonical homomorphism $A \to \Pi_E X$ (corresponding to $\mathrm{id} : X \to X$), which one might think of as sending an element of $A$ to the "best approximation" by a function on $E$.

It is probably more instructive to look at the following example. Let $E \times (-)$ be the comonad with counit $E \times X \to X$ defined by projection and comultiplication $E \times X \to E \times E \times X$ induced by the diagonal of $E$. What are the coalgebras of $E \times (-)$?

• Ok, thanks—I think I've just about understood this. It was dawning on me that what I'd written down for my $g$ above looked like a coalgebra. – Jeff Russell Jul 15 '14 at 22:41

The basic observation is that for every set $E$ we have the following comonoid structure $\Delta \colon E \to E \times E$ and $\epsilon \colon E \to *$, where $\Delta$ is the diagonal morphism and $\epsilon$ is the unique morphism from $E$ to the terminal object (this is also the unique comonoid structure that can be posed on a set).

Now applying the yoneda embedding $y \colon \mathbf {Set} \to [\mathbf{Set},\mathbf{Set}]$ to such monoid we get a monoid in $[\mathbf {Set},\mathbf {Set}]$ which gives exactly the monad structure (of course you have to use the fact that ${{-}^E}^E\cong{-}^{E \times E}$).

• The question was not how to construct the monad structure. – Martin Brandenburg Jul 15 '14 at 19:52
• @MartinBrandenburg The OP asked "Is there a more natural way to describe these things?" I presented such monad as the image of the comonoid through the yoneda embedding, isn't it a different way to describe the monad? – Giorgio Mossa Jul 15 '14 at 19:54
• Yes but the question is about a description of its algebras. This is the question in the first line. – Martin Brandenburg Jul 15 '14 at 19:57
• I meant a more natural way to describe the algebras—but this is still really helpful for me! – Jeff Russell Jul 15 '14 at 19:59
• Should that last fact say $(-)^E \circ (-)^E \cong (-)^{E \times E}$? – Jeff Russell Jul 15 '14 at 20:10