5
$\begingroup$

List is known to be a monad. It takes a set and maps it to lists of elements of that set. The natural transformations are, singleton and flatten, whereby we map a set to a set of singleton lists each with one element, and we take lists of lists and flatten them into lists (somewhat like concatenating). Suppose we define two more natural transformations, copy and delete. Copy takes a list and maps it to a list of two lists, they being copies of the original list. Delete takes a list and maps it to the underlying set of the List functor. The Delete natural transformation seems a bit dubious. Does this form a monad that is also a comonad? Here we have a paper that seems to suggest that non-empty list is a comonad. Does this apply to the example I am talking about?

$\endgroup$
  • 4
    $\begingroup$ On a set $A$, your counit should have a component $\mathrm{List}(A)\to A$, while your proposal of mapping a list to its underlying set seems to be a map from $\mathrm{List}(A)$ to the power set of $A$. Could you elaborate a bit on what the counit is? $\endgroup$ – Tobias Fritz Apr 29 '16 at 22:36
  • 9
    $\begingroup$ If $A$ is the empty set, then there is no map $\text{List}(A) \to A$, so there is no counit map as a natural transformation $\text{List} \to \text{Id}_{\text{Set}}$ between functors on the category of all sets. If you are committed to the category of all sets, this would be a problem. $\endgroup$ – Todd Trimble Apr 29 '16 at 23:56
  • $\begingroup$ Thanks everyone for your input @Tobias, I meant as a counit, a map from the elements of the list to $X$, where the endofunctor of the monad is $List: X -> List(X)$. I am now thinking you could map any list to the set of it's elements, then an injection into the set X. $\endgroup$ – Ben Sprott Apr 30 '16 at 1:52
  • 3
    $\begingroup$ Although this was a poorly thought-out question, @TomLeinster's answer justifies re-opening it. Indeed, I notice that most of those who voted to close it have no involvement in category theory, as recorded on this site. $\endgroup$ – Paul Taylor May 4 '16 at 19:36
15
$\begingroup$

Todd's comment provides an important limitation on what you can do here, but here's what I think is the most interesting way to answer your question. Define an endofunctor $L^+$ on the category of sets by $$ L^+(X) = \sum_{n \geq 1} X^n $$ for sets $X$, where $\sum$ means coproduct (disjoint union). Thus, an element of $L^+(X)$ is a nonempty finite list of elements of $X$.

Then $L^+$ can be given the structure of both a monad and a comonad.

The monad structure is the same as the one you described for possibly-empty lists: the unit sends $x \in X$ to the single-element list $x$, and the multiplication is concatenation ("flattening"). Its algebras are semigroups.

The comonad structure is less well-known (at least, to mathematicians; it seems better known in computer science). The counit map $L^+(X) \to X$ sends a list $(x_1, \ldots, x_n)$ to $x_1$. The comultiplication $L^+(X) \to L^+(L^+(X))$ forms the "tails" of a list; for instance, $$ (x_1, x_2, x_3, x_4) \mapsto ((x_1, x_2, x_3, x_4), (x_2, x_3, x_4), (x_3, x_4), (x_4)) $$ and the general definition is what you'd guess from this.

(In fact, there's a relationship between the monad structure and the comonad structure on $L^+$, or more exactly a mixed distributive law between them, with $L^+$ itself as its underlying functor. In the terminology that some people use, this makes $L^+$ into a "bimonad".)

More generally, it sounds like you're looking for examples of monads that are also comonads. There are many of these: e.g. for any monoid $M$, the endofunctor $M \times -$ on the category of sets is both a monad and a comonad in a natural way.

$\endgroup$
  • 8
    $\begingroup$ That's a nice comonad! Interestingly, you can obtain another comonad on the same functor $L^+$ by using cyclic shifts instead of tails. I am wondering what its coalgebras are and whether it might shed some light on necklaces and the Burrows-Wheeler and Gessel-Reutenauer transforms. $\endgroup$ – darij grinberg May 3 '16 at 20:03
  • 3
    $\begingroup$ You probably already figured this out, @darij, but I think coalgebra structures on X for the cyclic shift comonad are given by a permutation of X and an assigment of positive integer multiplicities to the cycles of the permutation. The structure map sends an element x of X to the cycle of the permutation containing it concatenated with itself as many time as the multiplicity of the cycle indicates. $\endgroup$ – Omar Antolín-Camarena May 13 '16 at 19:24
  • 3
    $\begingroup$ And coalgebras for the tails comonad are rooted forests (by that I mean a graph which is a disjoint union of trees, each with a root). If you have a rooted forest with vertex set X, you get a coalgebra structure by sending each x in X to the path from x to the root of its component. $\endgroup$ – Omar Antolín-Camarena May 13 '16 at 19:26
  • 2
    $\begingroup$ Well, I guess you could just keep the formulas for the cyclic shift comonad but change the underlying functor to "non-empty sequences of distinct elements". I think that works and gives you a comonad whose coalgebras are permutations, but I haven't checked carefully. $\endgroup$ – Omar Antolín-Camarena May 13 '16 at 19:34
  • 2
    $\begingroup$ WOW! And no, I have not "already figured this out"; the time I have at my hands recently is very limited. But this is too good to be left unexplored; I will return to it soon enough! The appearance of permutations with marked cycles significantly corraborates the Gessel-Reutenauer connection (which admittedly was a piece of tinfoil back when I suggested it, but now looks almost inevitable). $\endgroup$ – darij grinberg May 13 '16 at 20:50

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.