Category Theory Dump 3

Algebraic Data Types

  • You can treat algebraic equations like composite types, and vice-versa

Discrete Category

  • “How do we represent a single set as a category?”
  • Sets do not have structure, but morphisms between objects imply structure
  • Category in which there are no morphisms beyond identity ones


  • A functor maps one category into another
  • A functor maps an object in one category into an object in another
  • A functor also maps each MORPHISM in one category into a morphism in another
  • A functor maps the homset (set of morphisms between any pair of points) of one category into another
    • e.g. homset for category C, C(a, b) and a homset for category D, D(fa, fb)
  • A functor is a potentially huge number of separate functions
    • One big function that maps objects in one category to those in the other
    • One function per morphism in the homset that maps each morphism to the other morphism in corresponding homset (?)
  • Functor has to preserve structure
    • Structure is defined in a category through composition
    • COMPOSITIONS must also be mapped by functor
  • Information can be added/lost (through non-injective, non-surjective morphisms) but structure must be preserved
    • ‘Faithful’ functor
      • Injective on homsets
    • ‘Full’ functor
      • Surjective on homsets
    • ‘Fully faithful’ functor
  • Endofunctors
    • Mapping within one category
    • Then aren’t all morphisms functors?!
      • OK: Not all morphisms “map”, not all morphisms are functions, some are relations, and there are other kinds of morphisms too
  • Most functors used in programming deal with only one category – that of sets and types

Functors in Programming

  • Objects are types
  • Morphisms are functions
  • A functor is a mapping of types
  • A functor is a total mapping – every object and morphism must be mapped
  • In Haskell these are ‘type constructors’
  • A functor must also map functions
  • Even after all mappings been defined, does it meet the conditions (functor laws)?
    • Every functor must preserve
      • Composition
      • Identity
  • Intuition
    • Functors as containers

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