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?



What is the (Co)Monad for a Bag
The answer is essentially already in the comments. Commutativity erases a monoid's sense of order, so the free *commutative* monoid monad is the 'bag monad' even if the free monoid monad is the 'list monad'.


Even Haskell requires some squinting if you want its structures to look like true monads (see: <http://math.andrej.com/2016/08/06/hask-is-not-a-category/>). On top of that, popular data structures that consist of key-value pairs with unique keys (they go by different names in different languages) aren't monads.


Comonads have co-units. To support those, comonadic data structures like non-empty lists typically have a root element. An empty bag doesn't have any elements and therefore bags cannot be comonads. 


