Connection between F-Algebras and algebras for a monad

Question

I've been reading up on functional programming, and I've come across two "algebra" notions which seem similar:

• An F-Algebra $F A \rightarrow A$ which captures the signature of the operations of, say, a monoid (https://en.wikipedia.org/wiki/F-algebra#Groups).
• An algebra for a monad, $T A \rightarrow A$. In this video, monoids are presented as algebra for the free monoid monad.

Is there any connection between these two concepts, or are they just superficially similar?

Answer 1

On the one hand, one can answer that $F$-algebras for an endofunctor $F: \mathcal{C}\to\mathcal{C}$ are more general than EM-algebras for a monad $T: \mathcal{C}\to\mathcal{C}$ (EM-algebras = Eilenberg-Moore algebras for a monad $T$) in the sense that: the EM-category for $T$ (i.e. the category of EM-algebras for $T$) is a full subcategory of the category of $T$-algebras.

But there is also another direction meaning that EM-algebras are more general: the category of $F$-algebras is itself the EM-category for a particular $T$, if for any $C\in \mathcal{C}$ the functor $G X= FX+C$ has an initial algebra. Inuitively, an EM-algebra for a monad $T$ evaluates finite $T$-terms preserving the laws of the theory and an $F$-algebra evaluates a flat term within the theory of $F$-terms without any further laws to obey.

Let $TC$ be the carrier of the initial $G$-algebra and let $g_C$ be its algebra structure: $$ g_C: F(TC) + C \longrightarrow TC. $$ For some $h: C\to D$, define $Th$ by recursion using the $G$-algebra $g_D\cdot (\mathsf{id}+h)$: $$ \matrix{ &FTC+C& \xrightarrow{g_C} && TC \\ {FTh+C}\swarrow &\quad\quad\searrow& & & \downarrow\rlap{=: Th} \\ FTD+C &\smash{\xrightarrow{\mathsf{id}+h}} &FTD+D & \smash{\xrightarrow{g_D}} &TD } $$ This diagram also proves that $g_{(-)}$ is natural.

Then one can show that $T$ is a monad on $\mathcal{C}$: its unit is $\eta_C = g_C\cdot \mathsf{inr}: C\to TC$ and its multiplication is defined by recursion again: $$ \matrix{ FTTC + TC & \xrightarrow{\quad g_{TC}\quad} & TTC \\ \llap{F\mu_C+\mathsf{id}_{TC}}\downarrow && \downarrow\rlap{\mu_C} \\ FTC + TC & \smash{\xrightarrow{[g_C\cdot \mathsf{inl},\mathsf{id}]}} & TC } $$ $T$ is called the free monad on $F$, which can be intuitively thought of mapping a set $C$ to the finite $F$-terms over $C$. Now there is a one-to-one correspondence between $F$-algebras and EM-algebras for $T$: for any $F$-algebra $a:FA\to A$, we obtain a EM-algebra for $T$ by $$ FA+A \xrightarrow{[a,\mathsf{id}_A]} A $$ and conversely any EM-algebra $b: TB\to B$ induces an $F$-coalgebra $b\cdot g_B\cdot \mathsf{inl}\cdot F\eta_B: FB\to B$.

Answer 2

An $F$-algebra is the generalization of an algebra for a monad to the case where have monad $T$ may be an arbitrary endofunctor. Note that the structure of an algebra for a monad is again a map $TA\to A$, not $TA\to T$ as in your question.