winterkoninkje: Shadowcrane (Default)
[personal profile] 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).

Tags:

Profile

winterkoninkje: Shadowcrane (Default)
wren gayle romano

August 2014

S M T W T F S
     12
34 56 789
1011121314 1516
171819 20212223
24252627282930
31      

Common Tags