Category Theory Dump 2

Kleisli Category

  • The Kleisli category of C is the corresponding category CT
  • Every morphism f: X → T Y in C (with codomain TY) can also be regarded as a morphism in CT (but with codomain Y)
  • The ’embellishing implementation’ in C (the mapping which returns a new type that is a pair of the input type with some embellishment) is a regular morphism in the corresponding Kleisli category CT (it is also called a ‘monad’)

Universal Construction

  • Everything should be reasoned about in terms of morphisms/arrows:
    • Direction (ingoing/outgoing)
    • An object is defined in relation to every other in the category
    • “Show me all matches for this pattern”
    • “What is the best candidate out of these matches?”

Terminal and Initial Objects

  • A terminal object is one that all the other objects in the category point to/converge on, i.e. every other object has an arrow pointing towards the terminal object
    • In the SET category, it is a singleton set/type

Opposite Category


  • Product is an object c with two projections to a and b
  • There are a lot of objects that have two projects, but the product has to be the ‘best’ candidate
  • Candidates are ranked in terms of injectivity (monomorphism, 1-to-1) and surjectivity (codomain is covered by the image mapping), i.e. the degree of information loss and information redundancy, respectively
  • Poorer candidates (e.g. c-prime) can be reduced to the best candidate c, through a unique morphism m
  • “pair(a, b)”
  • fst and snd are ‘destructors’ of the product, extracting one of the pair (projections)
  • Is a monoid


  • Inverse of products
  • Coproduct is an object with a pair of injections going into it, such that for any other object with two injections going into it, there is a unique morphism m, from c to c-prime, c-prime being the poorer candidate
  • Again, there are many possible candidates for c, so we have to use universal construction to find the best one
  • The best candidate is a union of a and b in terms of sets
    • The best candidate is a discriminated union of a and b if a and b are identical
    • Discriminated union / tagged union / variant
    • Pair contains ‘both types’ of a and b, whereas a union contains ‘either’ a or b
    • An enumeration/enumerable?
    • An Either type
    • Either a b = Left a | Right b
      • Left a and Right b are constructors (injections)
      • A struct or a class with two constructors
    • How do we extract from an Either?
      • Can’t simply say we want one of the two types a or b, because we don’t know which one it was constructed with
      • Both possibilities have to be taken into account
  • Is a monoid

Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s