8
$\begingroup$

I may be wrong, but we should be able to write the Bag monad in a polynomial form. The bag monad, is exectly the multiset monad whose category of algebras are the commutative monoids. Another name for the bag monad is a container.

Containers are synonymous with polynomail functors. The data that defines a container are precisely the following morphisms in a locally Cartesian closed category $C$:

$$ 1 \xleftarrow{\text{f}} X \xrightarrow{\text{g}} Y \xrightarrow{\text{h}} 1 $$

Where $1$ is the terminal object in $C$. This defines an endofunctor for which there is a monad. Specifically, the endofunctor is :

$$ C/W \xrightarrow{\text{f^* }} C/X \xrightarrow{\Pi_g} C/Y \xrightarrow{\Sigma_h} C/Z $$

We are interested in endofunctors so $W$ and $Z$ are $1$ in $Set$.

What is the polynomial form of the bag monad?

$\endgroup$
13
$\begingroup$

The bag monad is not polynomial.

Any polynomial endofunctor must preserve pullbacks: $f^*$ and $\Pi_g$ preserve all limits since they’re right adjoints, while $\Sigma_h$, being just the forgetful functor from a slice category, is well known (and easily seen) to preserve all connected limits.

However, the bag monad doesn’t preserve pullbacks. Write $B$ for the bag monad, and consider the sets $X = \{a,b\}$, $Y = \{y,z\}$, and view their product as a pullback, $X \times Y = X \times_1 Y$. Then the canonical map $B(X \times Y) \to B(X) \times_{B(1)} B(Y)$ fails to be injective, since $\{(a,y),(b,z)\}$ and $\{(a,z),(b,y)\}$ are distinct in $B(X \times Y)$ but have the same image in $B(X)$ and $B(Y)$.

This example — and the fact that commutativity forms an obstacle to being polynomial, and similar sorts or representation — has appeared notably before in the literature, in for instance the note 3-computads do not form a presheaf category by Michael Makkai and Marek Zawadowski, and (essentially) in Carlos Simpson’s paper Homotopy types of strict 3-groupoids.

$\endgroup$
1
10
$\begingroup$

The free multiset functor is not polynomial in the standard sense; it is though in a categorified sense if you somehow keep track of the different ways two expressions are the same thanks to commutativity: for that you need to pass from the category Set to the 2-category of groupoids. See Data Types with Symmetries and Polynomial Functors over Groupoids.

$\endgroup$
1
  • $\begingroup$ thanks for the link Eduardo. It was tough choosing which answer to mark. $\endgroup$ – Ben Sprott Jun 12 '18 at 17:45

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.