2
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 14
    $\begingroup$ You might get better answers if you give a mathematical definition 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, 2018 at 15:21
  • 6
    $\begingroup$ FWIW, not all data structures are monads. $\endgroup$
    – Mike Shulman
    Jan 26, 2018 at 16:00
  • 2
    $\begingroup$ In particular, the "multiplication" is exactly what you might guess: it maps a bag of bags of things to a bag of things by dissolving the inner bags leaving all their contents in the outer bag. $\endgroup$
    – Dan Piponi
    Jan 26, 2018 at 22:30
  • 2
    $\begingroup$ Since, unbelievably, no one has done so yet, let me point out the obvious and record the usual: Tom Leinster's above comment is entirely correct. Some usual terminology has not been mentioned yet: the most usual synonym for 'bag' in mathematics theses days is multiset. 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, 2018 at 8:25
  • 3
    $\begingroup$ ''occurrence set'', ''heap'', ''sample'', and ''fireset'' --finitely repeated element set.'' 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, 2018 at 8:29

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.