An important notion that shows up in algebra is the idea of a free object. For example, we have the following free objects for their corresponding algebraic theories:
NonemptyList A— free semigroups
List A— free monoids
NonemptyBag A— free commutative semigroups
Bag A — free commutative monoids
NonemptySet A— free commutative bands (band = idempotent semigroup)
Set A— free commutative bands with identity
Recently I've been coming across things whose quotient structure looks like:
Foo A B = List (NonemptyMap A (NonemptyList B)) Bar A B = (Foo A B, NonemptyList (A,B))
I'm curious if anyone has encountered either of these as free objects of some algebraic theory?
 I.e., a multiset. In order to get the proper quotienting structure, we can implement
Bag A by
Map A Nat where
a `elem` xs = member a xs and
multiplicity a xs = maybe 0 (1+) (lookup a xs).