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
  • 2
    @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
  • 1
    Thanks for the comment. I've added more detail to the question. – Jeff Russell Jul 15 '14 at 19:34
up vote 6 down vote accepted

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
  • 2
    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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.