winterkoninkje: shadowcrane (clean) (Default)

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

January 2017

S M T W T F S
1234567
891011121314
15161718192021
22232425262728
293031    

Tags

Page generated 24 Feb 2017 12:35 pm
Powered by Dreamwidth Studios