Algebras of the environment monad

Question

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$.

Answer 1

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 (-)$?

Answer 2

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}$).