3
$\begingroup$

It is well-known that if $T\colon\mathrm{Sets}\to\mathrm{Sets}$ is the monad which takes a set $S$ to the set of lists of elements of $S$, i.e., $\bigsqcup_{n\ge0} S^n$, with the monad structure $\mu\colon T\circ T\implies T$ given by concatenation, i.e., $$ S^{k_1}\times\cdots\times S^{k_m}\xrightarrow\mu S^{k_1+\cdots+k_m}: ((x_{1,1},\dots,x_{1,k_1}),\dots,(x_{m,1},\dots,x_{m,k_m}))\mapsto (x_{1,1},\dots,x_{1,k_1},x_{2,1},\dots,x_{m,1},\dots,x_{m,k_m}),$$ then $T$-algebras (as defined in VI.2 of Maclane Categories for the Working Mathematician) is equivalent to the category of monoids, hence $T=U\circ F$, where $U\colon \mathrm{Mon}\to\mathrm{Set}$ is the forgetful functor, and $F\colon\mathrm{Set}\to\mathrm{Mon}$ is the free monoid functor (See, e.g., Defining multiplication transformation for free monoid monad on monoidal category)

I am interested in replacing $T$ by $T^* \colon\mathrm{Sets}\to\mathrm{Sets}$, the monad which takes $S$ to the set of lists of possibly countably infinite elements of $S$, i.e., $\bigsqcup_{n\ge0}S^n\sqcup S^{\mathbb N}$, again with monad structure $\mu\colon T^* \circ T^* \implies T^*$ given by concatenation (from left to right).

What is the category of $T^*$-algebras?

If $M\in T^* \mathrm{-alg}$ then it comes with a map $T^* M:=\bigsqcup_{n\ge0}M^n\sqcup M^{\mathbb N}\to M$. Concretely, the restriction to $TM\subset T^* M$ gives $M$ the structure of a monoid. But $M$ also comes with a strange infinite-ary operation $\mu_{\mathbb N}\colon M^{\mathbb N}\to M$. The image of $\mu_{\mathbb N}$ lands in the sub-set $ \{x\in M:\forall y\in M,xy=x\} \subset M$, since concatenation from the right with infinite lists does nothing. However, I am interested in a more concrete description of the category $T^* \mathrm{-alg}$.

$\endgroup$
11
  • 3
    $\begingroup$ How do you propose to concatenate two infinite lists, i.e.what explicitly is the monad multiplication you have in mind? $\endgroup$ Commented Oct 10, 2023 at 23:34
  • 2
    $\begingroup$ I propose to just take the first infinite list. $\endgroup$
    – Kenta S
    Commented Oct 10, 2023 at 23:38
  • 1
    $\begingroup$ Hmm, maybe it's fine. I suppose more generally the proposed concatenation of a possibly infinite list of possibly infinite lists is to concatenate from left to right until the list becomes infinite, then stop? $\endgroup$ Commented Oct 11, 2023 at 4:03
  • 1
    $\begingroup$ Also, several times in this post you say "monad" when you mean "monoid" which I imagine could be confusing to some readers. $\endgroup$ Commented Oct 11, 2023 at 4:06
  • 1
    $\begingroup$ Hmm, we might actually not have a monad here. From your description, I would expect $\mu_X : [ [], [], [], \ldots ] \mapsto []$ which is the identity of the monoid $T^* X$. On the other hand, since $(T^* X, \mu_X)$ must be a $T^*$-algebra, you would expect the image of $[ [], [], [], \ldots ]$ to be a right-absorber, giving a contradiction. So in other words, associativity doesn't work on $[ [ [], [], [], \ldots ], [ [x] ] ]$. $\endgroup$ Commented Oct 11, 2023 at 16:55

1 Answer 1

4
$\begingroup$

The functor $T^*$, with the given $\eta$ and $\mu$, do not form a monad. To see this, consider a nonempty set $X$ with $x \in X$, and look at the condition for associativity on the element $[[[], [], [], \ldots], [[x]]] \in (T^*)^3 X$. On the one hand, $\mu_{T^* X}$ maps this to $[[], [], [], \ldots]$, and applying $\mu_X$ gives $[]$. On the other hand, $T^* \mu_X$ maps the element to $[[], [x]]$, and applying $\mu_X$ gives $[x]$. Therefore, the associativity condition fails.

In fact, it is easy to see there is no monad on the functor $T^*$ which extends the list monad. To see this, we have $[[], [], [], \ldots] \in (T^*)^2 \emptyset$, and the only possible image for $\mu_\emptyset$ of this element in $T^* \emptyset$ is $[]$. Then, by the naturality of $\mu$, we must have $\mu_X : [[], [], [], \ldots] \mapsto []$ for all sets $X$. As in the previous paragraph, this gives a contradiction.


So at this point, some computer scientist out there might wonder: OK, but the syntactic monad described (which is not semantically a monad) is exactly what the Haskell version of lists amounts to, and we have concrete definitions of the list monad in Haskell. The resolution: the join operation on $[[], [], [], \ldots]$ will actually enter an infinite loop when trying to head-reduce the result. So, the join operation of the Haskell list monad is not actually a total function.

It might be possible to model this mathematically by extending the functor to include a possibility of a "partial finite list followed by an infinite loop condition". Then, for example, you could map the infinite list of empty lists to an empty list followed by an infinite loop condition.

$\endgroup$
2
  • $\begingroup$ Thank you for the answer! Indeed, the motivation for the question came from what the list monad in Haskell is mathematically. $\endgroup$
    – Kenta S
    Commented Oct 11, 2023 at 19:10
  • 1
    $\begingroup$ Another option to resolve this is to consider it a monad not on the category of sets but on some category of partial functions (for example Hask, if you're willing to overlook the question of whether Hask is a category). Then the join operation on $[[],[],[],\dots]$ can just fail to terminate, as it should. This is different from your suggestion because this way an algebra will be a set $M$ equipped with a partial function $T^*(M)\to M$ (plus equations). I think this partiality might be connected to the idea that a series might not converge. (@KentaS you might be interested in this comment.) $\endgroup$
    – N. Virgo
    Commented Oct 12, 2023 at 3:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .