Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: the list functor

Naso (Apr 06 2021 at 14:42):

The list functor $L$ is often considered in computer science, it sends a set $X$ to the set of lists on $X$.
A list on $X$ can also be thought of as a linearly ordered multiset with elements in $X$.
That functor can be made a monad with multiplication as list concatentation.

Can we also have a functor that sends $X$ to the set of partially ordered (or preordered) multisets with elements in $X$, and would it also be a monad?

I feel that it should be, but I can't find any mention about it which makes me doubt.

Kenji Maillard (Apr 06 2021 at 14:53):

The multisets $\mathcal{M}X$ on a set $X$ do form a monad, with unit sending an element $x \in X$ to the multiset containing one occurence of $x$ and multiplication $\mu_X : \mathcal{M}\mathcal{M}X \to \mathcal{M}X$ sending a multiset of multiset of $X$ $\Sigma_{i} a_i \cdot \Sigma_j b_{ij} \cdot x_{ij}$ to the multiset $\Sigma_{(i,j)} (a_ib_{ij})\cdot x_{ij}$ (where I'm writing a multiset as a formal sum of its elements).

Naso (Apr 06 2021 at 15:02):

Thanks @Kenji Maillard . What do you think about a partially/pre-ordered multiset monad, do you think there's any problem with it? It seems if we had a preorder of preorders we could "squash" it into just a preorder (sorry I can't think how to express that properly & concisely), the unit sending $x$ to the singleton preorder with $x$.

Oscar Cunningham (Apr 06 2021 at 15:07):

Nasos Evangelou-Oost said:

sorry I can't think how to express that properly & concisely

"Compare by the outer partial order and then by the inner one"?

Naso (Apr 06 2021 at 15:08):

@Oscar Cunningham yes that's what I mean :) By the way partially ordered multisets are sometimes called "pomsets", so maybe it should be called the pomset monad if indeed it is one.

Kenji Maillard (Apr 06 2021 at 15:09):

In category theory (by opposition to computer science here), a monad is an endofunctor, so if it takes sets as input it should spit out sets as well, not a preorder. If you really want to insist on the fact that the result has a preorder structure, I would forward you to the notion of relative monad (in the case at hand, relative to the functor sending a set to the preorder with the same underlying set and the trivial/discrete order)

Oscar Cunningham (Apr 06 2021 at 15:10):

My understanding is it takes a set to the set of pomsets on it

Kenji Maillard (Apr 06 2021 at 15:10):

Wait, do you assume that $X$ is ordered ?

Oscar Cunningham (Apr 06 2021 at 15:11):

It looks like a monad to me. I wonder what its algebras are? They have quite a lot of structure. You can get a commutative monoid structure on them by looking at the unordered pomsets, and a different (?) monoid structure by looking at the totally ordered pomsets.

Naso (Apr 06 2021 at 15:11):

Kenji Maillard said:

Wait, do you assume that $X$ is ordered ?

No. And yes I was thinking of this as an endofunctor on $Set$, since it takes a set to the set of pomsets on it as @Oscar Cunningham said.

Mike Stay (Apr 06 2021 at 15:16):

@Nasos Evangelou-Oost You have to be a little careful.

There's the "free monoid" monad that takes a set to the underlying set of the free monoid on the set. The words of the free monoid are finite lists, so while they are linearly ordered multisets, they are also finite.

There's also the List algebraic data type $L_X:Set \to Set$ where $L_X(R) = X\times R + 1,$ the sum of cons ($X \times R$) and nil ($1$). (I used the variable $R$ as a mnemonic for "recursion point".) Then the initial algebra of the functor happens to be the same as the free monoid on $X$, but the terminal coalgebra of the functor gives "streams", potentially infinite lists of elements of $X$. These are also linearly ordered multisets, but they're at most countably infinite.

As @Kenji Maillard pointed out, you can get all multisets on $X$ as a monad. You want all partially ordered multisets, which is extra structure. If you're willing to restrict to finite or countably infinite structures, you could use a rooted directed acyclic graph (r-dag) labeled by elements of $X.$ In an r-dag of r-dags of Xs, each node $n$ in the larger structure contains an r-dag. You can define flattening to make the parents of the root of the contained r-dag be the union of the sets of tips of the r-dags contained in the parent nodes of $n.$ The unit takes each element $x$ of $X$ to the r-dag whose root is labeled by $x.$

Mike Stay (Apr 06 2021 at 15:18):

That assumes a least element. If you want arbitrary partial orders, then you simply use a labeled dag; you can define concatenation in a similar way, where the parents of each "root" are as above.

Naso (Apr 06 2021 at 15:23):

@Mike Stay in what I had in mind restricting to finite or countably infinite is not a problem, but I'm not sure I see what you mean about DAGs-- why do I need this, I mean why can't I simply define the endofunctor $P$ on $Set$, $P X =$ the set of partially ordered multisets on $X$?

Naso (Apr 06 2021 at 15:27):

(I'm not sure exactly what you mean by "extra-structure" either... isn't a labelled DAG also extra structure? And then I should also take the transitive closure to recover the partial order? But I'm not sure what problem this solves.)

Mike Stay (Apr 06 2021 at 15:28):

Every dag has an induced partial order on its set of vertices and every partially ordered finite set has a corresponding dag where $a$ is a parent of $b$ if $a < b$ and there does not exist $c$ such that $a < c < b$. So if you're ok to use finite or countably infinite structures, dags are the obvious way to tell a computer about it.

Mike Stay (Apr 06 2021 at 15:29):

But yes, you can just use that endofunctor on Set and the concatenation operation I described.

Naso (Apr 06 2021 at 15:30):

Oh I'm not really worried at this point in encoding it in a computer, I was just wanting to know whether there was any mathematical problem with defining a pomset (or preorder) monad.

Mike Stay (Apr 06 2021 at 15:41):

No, that's a perfectly good monad assuming I didn't miss something in defining concatenation. You should check the associativity and unit laws for the definition I gave (which I made up on the spot).

Oscar Cunningham (Apr 06 2021 at 15:46):

It has a distributive law!
image.png
Actually that diagram is wrong. The right hand side should look like $K_{2,2}$. Hmmm.

Naso (Apr 06 2021 at 15:48):

@Mike Stay ok, I will check them. So to clarify, would you say there is no real difference whether I define it in terms of labelled dags or pomsets? With the dag I have to have the extra assumption that "there does not exist $c$ such that $a < c < b$". Also I'm not 100% clear on what the finite/countably-infinite assumption is for. Actually the pomsets I'm interested in are the ones which are interval-finite, i.e. $\forall{x,y} . \lbrace{z | x \leq z \leq y\rbrace}$ is finite (https://ncatlab.org/nlab/show/causet#definition), I'm not sure whether this implies countably-infiniteness?

Mike Stay (Apr 06 2021 at 15:54):

I thought you were coming at the question from a programmer's perspective. If you're not interested in implementing it on a computer, then you can ignore all that stuff; it's all implementation details. The finite/countably infinite stuff is a side-effect of using algebraic data types and the fact that all computable sets are at most countably infinite. The $a < c < b$ stuff is because you need to know the set of parents of a vertex, not just its ancestors, to construct the dag.

Since you're more of a mathematician, you just have to figure out a multiplication and a unit for the monad; I gave a suggestion which you should check.

Naso (Apr 06 2021 at 15:56):

@Mike Stay got it! Thanks for your comments. Thank you @Kenji Maillard & @Oscar Cunningham as well.

Naso (Apr 06 2021 at 15:57):

@Oscar Cunningham I'm curious about what you're trying to show with that picture. What do you mean it has a distributive law? I only knew about distributive laws between two different monads.

Oscar Cunningham (Apr 06 2021 at 15:58):

Do you know about algebras of monads?

Naso (Apr 06 2021 at 15:59):

@Oscar Cunningham I know about F-algebras for ordinary functors, I'm not sure what the extra monad structure does for it

Oscar Cunningham (Apr 06 2021 at 16:01):

Algebras for a monad are the same thing, except they have to obey some laws involving the unit and multiplication of the monad.

Oscar Cunningham (Apr 06 2021 at 16:04):

In particular it turns out that algebras of the List monad are precisely monoids, and algebras of the multiset monad are precisely commutative monoids (because a monoid is a place where it makes sense to multiply together a list of elements, whereas in a commutative monoid order doesn't matter so you can multiply together a multiset of elements).

Oscar Cunningham (Apr 06 2021 at 16:07):

Since your monad combines both, you have a monoid structure and a commutative monoid structure on the algebras, which you could think of as $\times$ and $+$. They're defined by $a\times b$ being the image under the map defining the algebra of the pomset $a<b$, and likewise $a+b$ corresponding to the pomset where a and b are incomparable. Then I thought we had the distributive law $(a+b) (c+d) = ac + ad + bc + bd$, but in fact it's more complicated than that.

Naso (Apr 06 2021 at 16:11):

I see, this is very interesting!

Tom Hirschowitz (Apr 07 2021 at 12:35):

@Mike Stay How do you ensure that the result of your concatenation will again by acyclic? E.g., if the outer r-dag is the walking arrow $0 \leq 1$, the label of $0$ is $a \leq b$ and that of $1$ is $b \leq a$, don't you get a loop around $a$ and $b$?

Mike Stay (Apr 07 2021 at 13:25):

@Tom Hirschowitz A similar problem arises in the list case, thinking of it as a linear order: [a,b]++[a] makes a ≤ b ≤ a, which is no longer linearly ordered. I assumed that the linear order/partial order was on the vertices, and the "multiset" aspect was the function from the vertex set to the label set.

Tom Hirschowitz (Apr 07 2021 at 14:02):

Ah, right, it's about occurences of letters, not letters themselves. Thanks!

Ben Sprott (Apr 10 2021 at 15:06):

@Mike Stay Hi Mike, since you are here, can you field this question I've had for a while? It's related. I was trying for a while to construct the DCPO (co)monad. It has a functor that takes a set X to the set of all DCPOs on X. I wanted to squash a DCPO of DCPO's to form the product of the monad and then create "histories" of a DCPO to form the co-product of the comonad.

Mike Stay (Apr 10 2021 at 21:17):

Sorry, I've never learned what a DCPO is.

Ben Sprott (Apr 11 2021 at 02:16):

For anyone reading, a DCPO is a directed complete partial order. They are also known as domains.