### In search of algebraic theories

Jul. 14th, 2013 10:44 pm**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)`

.