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?

Peter LeFanu Lumsdaine 06/12/2018 at 17:09.

**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*.

Eduardo Pareja Tobes 06/12/2018 at 17:06.

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.

- Is the evaluation of polynomial functors appropriately continuous?
- What sort of W-types follow from existence of an NNO?
- When is the endofunctor category of a monoidal category braided? When is it ribbon? Fusion? Modular?
- “Maybe Monad” for multi-pointed objects?
- To what kind of generalized Lawvere theory does the “free cartesian closed category” 2-monad on $\mbox{Cat}_g$ correspond?
- Closure of polynomial monads under colimits
- What are the axioms of the diagrammatic calculus for containers?
- Is Det-Stoch a factorization of the Giry Monad?
- When is an algebra a container? Can we compute the container for an algebra?
- On functors preserving monoid objects