2
$\begingroup$

Preliminaries
A monad is a triple $(M, \eta, \mu)$, with $M$ a functor, $\eta : \mathit{id} \Rightarrow M$ and $\mu : M^2 \Rightarrow M$ two natural transformations such that the following diagrams commute.
For example, the triple $M_L = (L, \eta_L, \mu_L)$ is the non-empty list monad, with $L X = X^+$ (i.e., non-empty lists), $\mu_L([l_1, ..., l_n]) = l_1 \ \mathrm{++}\ ...\ \mathrm{++}\ l_n$ (i.e., concatenation), and $\eta_L(x) = [x]$ (i.e., singleton list) for $x \in X$.

A comonad is a triple $(W, \epsilon, \delta)$, with $W$ a functor, $\epsilon : W \Rightarrow \mathit{id}$ and $\delta : W \Rightarrow W^2$ two natural transformations such that the following diagrams commute.
For example, the triple $W_L = (L, \epsilon_L, \delta_L)$ is the non-empty list comonad, with $\epsilon_L([x_1, ..., x_n]) = x_1$ (i.e., returns the head of the list), and $\delta_L([x_1, x_2, x_3]) = [[x_1, x_2, x_3], [x_2, x_3], [x_3]]$ (i.e., returns the list of tails).

A distributive law of the comonad $(W, \epsilon, \delta)$ over the monad $(M, \eta, \mu)$ is a natural transformation $\xi : WM \Rightarrow MW$ such that the following diagrams commute.
As a candidate for a distributive law, we define the transformation $\xi_{L} : W_L M_L \Rightarrow M_L W_L$ that forms the list of lists that contain one element (in order) of each list in its argument. For instance, $$ [\{x_1, x_2\}, \{x_3, x_4\}, \{x_6\}] \mapsto \{[x_1, x_3, x_6], [x_1, x_4, x_6], [x_2, x_3, x_6], [x_2, x_4, x_6]\} $$ and the general definition is what you would guess from this.

Problem
As far as I can tell, the "natural" distributive law ($\xi_L$) that we could think of as defined above doesn't work. Indeed, the (bottom-left) axiom is violated: \begin{align*} 1_{M_L} \cdot \epsilon (\xi_L [\{1\}, \{2, 3\}]) &= 1_{M_L} \cdot \epsilon\ \{[1,2],[1,3]\} \\ &= \{1,1\} \\ &\not = \{1\} \\ & = \epsilon \cdot 1_M ([\{1\}, \{2,3\}]) \end{align*}

Changing the non-empty list monad to the non-empty set monad would solve the problem. The change is in $L X = \mathcal{P}(X)\setminus\{\emptyset\}$ with $\eta_L$ the singleton set, and $\mu_L$ the set union. We consider the same distributive law, that forms a set of lists that contain, in order, one element of each set in the argument list. Here, as well, we face a problem with now the (bottom-right) axiom: \begin{align*} (\xi\cdot 1_W) ((1_W \cdot \xi) ( (\delta \cdot 1_M) [\{1\}, \{2, 3\}])) &= (\xi\cdot 1_W) ((1_W \cdot \xi) ( [[\{1\}, \{2, 3\}], [\{2, 3\}]])) \\ &= (\xi\cdot 1_W) ([\{[1, 2], [1, 3]\}, \{[2], [3]\}]) \\ &= \{[[1, 2], [2]], [[1, 2], [3]], [[1, 3], [2]], [[1,3], [3]]\}\\ &\not= \{[[1, 2], [2]], [[1,3], [3]]\}\\ &=\xi ( (1_M \cdot \delta) [\{1\}, \{2, 3\}])\\ \end{align*}

Questions
As hinted in a previous answer by Tom Leinster, it is said that a distributive law exists between the non-empty list monad and the non-empty list comonad. Does there exist any result that witnesses the existence of a distributive law of the non-empty list comonad over the non-empty list monad? What if the non-empty set monad is replaced by the nonempty set monad (keeping the nonempty list comonad)? How would one prove that such distributive law does not exist?

$\endgroup$
0

0

You must log in to answer this question.

Browse other questions tagged .