A Bag is a data structure, like a list, that stores items with no concept of order. The only operations on the structure is to add an item and then iterate through the items with no guarantee as to the order of iteration. We see it in Sedgewick's Algorithms book. I am guessing this is a monad since it is very much like the list monad. What is the Monad for the bag? Is it a Comonad?

A more technical and mathematical definition for a bag would be a set with finite multiplicities. What is the monad for that? Is that functor also a comonad with suitable natural transformations?

mathematicaldefinition of bag. My possibly incorrect memory is that a bag is a set with finite multiplicities. In that case, given a set $X$, a bag with elements in $X$ is precisely an element of the free commutative monoid on $X$. So, bags are generated by the free commutative monoid monad. But I don't know whether that answers your question. $\endgroup$ – Tom Leinster Jan 26 '18 at 15:21multiset. To give a reference, let me cite [W. D. Blizard:Multiset Theory. Notre Dame Journal of Formal Logic, Vol. 30, No. 1, 1989; p. 37]: ''The word ''multiset'' [...] which abbreviates the term ``multiple-membership set'', is now the commonly accepted name for this concept, replacing ''bag'', ''bunch'', ''weighted set'', [...] $\endgroup$ – Peter Heinig Jan 27 '18 at 8:25finitelyrepeatedelementset.'' Apart from the formalization via free commutative monoids, the most usual formalization within usual set theory is 'multiset'='function from a set to $\omega$', with each function value interpreted as the multiplicity. $\endgroup$ – Peter Heinig Jan 27 '18 at 8:293more comments