I would like to see a full definition of the free commutative monoid monad. Here is what I have so far. We define it with these parts $FCMonoidMonad = (CM, \mu, \eta)$.

$$ CM : Set \rightarrow Set$$ ex $$CM(\{a\}) = \{e, a,a^{2},a^3 \dots\}$$

$$ \mu : CM \cdot CM \rightarrow CM $$ It has been pointed out that I have done the composition of the endofunctors incorrectly. Here I am trying again. I am thinking of getting a monoid of commutative monoids. So, my guess is this: $$CM \cdot CM (\{ a \}) = \{\{e, a,a^2,a^3 \ldots \}, \{e, a,a^2,a^3, \cdots\}, \cdots\}$$ Thinking of the list monad, we want to dissolve the sets, perhaps by taking the free product of all the elements of all the lists. This would return the single application of the functor: $$\mu(\{\{e, a,a^2,a^3 \ldots \}, \{e, a,a^2,a^3, \cdots\}, \cdots\}) \rightarrow \{e, a,a^2,a^3 \ldots \}$$

I also don't know how to define the $\eta$ $$\eta : 1_{Set} \rightarrow CM$$

Can someone check what I have done and also define $\eta$?

  • $\begingroup$ Your $\mu$ does not really work. Recompute the composition of the functor with itself. $\endgroup$ Feb 3, 2018 at 20:49
  • 1
    $\begingroup$ By the way, monoids have an identity. $\endgroup$ Feb 3, 2018 at 20:50
  • $\begingroup$ How did you get $CM \cdot CM (\{ a \}) = \{a,a^2,a^3 \ldots \}$? $\endgroup$ Feb 3, 2018 at 22:05

1 Answer 1


What you have done is incorrect; besides missing the identity element of $CM(\{a\})$, your formula for $CM(CM(\{a\}))$ is totally wrong (you seem to have forgotten to apply $CM$ a second time...) and you have not said anything about what happens for sets with more (or less) than one element.

The free commutative monoid on a set $S$ can be constructed explicitly as the set of all finite support functions $S\to\mathbb{N}$. That is, let $CM(S)$ be the set of all functions $f:S\to\mathbb{N}$ such that $f(s)=0$ for all but finitely many $s\in S$. These functions form a commutative monoid under pointwise addition, and are freely generated by $S$ via the map that sends $s\in S$ to the characteristic function of $\{s\}$. You should think of such a function as the formal sum of $f(s)$ copies of $s$ over all $s\in S$.

The map $\eta_S:S\to CM(S)$ is then just the inclusion of the free generators. That is, $\eta_S(s)$ is the characteristic function of $\{s\}$, the function $f:S\to\mathbb{N}$ defined by $f(t)=0$ if $t\neq s$ and $f(s)=1$.

The composition transformation $\mu$ is more complicated. The idea is that an element of $CM(S)$ is a formal sum of elements of $S$, so an element of $CM(CM(S))$ is a formal sum of formal sums of elements of $S$. You can turn a formal sum of formal sums into a formal sum by just combining everything into one big sum: for instance, $((2a+b)+(a+c)+(2b+d))$ should turn into $3a+3b+c+d$.

More formally, we can define the map $\mu_S:CM(CM(S))\to CM(S)$ as follows. Given $F\in CM(CM(S))$, $\mu_S(F)$ is the function $f:S\to\mathbb{N}$ defined by $$f(s)=\sum_{g\in CM(S)}g(s)\cdot F(g).$$ This sum makes sense because $F(g)=0$ for all but finitely many $g\in CM(S)$. Intuitively, if we think of $F$ as the formal sum of $F(g)$ copies of $g$ for each $g\in CM(S)$ and $g$ as the formal sum of $g(s)$ copies of $s$ for each $s\in S$, this sum is just what we get by "combining" all these sums into one big sum of elements of $S$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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