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).

Profile

winterkoninkje: Shadowcrane (Default)
wren gayle romano

March 2014

S M T W T F S
      1
2345678
9 101112131415
16171819202122
23242526272829
3031     

Most Popular Tags

Expand Cut Tags

No cut tags

Style Credit

Page generated Apr. 23rd, 2014 02:20 pm
Powered by Dreamwidth Studios