In search of algebraic theories

[winterkoninkje]

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 [1] — 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?

[1] 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).