My (random) thoughts on “Category Theory for Programmers”

I have been interested in programming for a while and functional programming especially. In order to improve my theoretical background, I have started reading book “Category Theory for Programmers” (PDF and sources here). In this article I would like to present some of my thoughts and answers to the questions in chapeters of these books.

You can see my solutions of challenges from book in my post My solutions of challenges in book „Category Theory for Programmers“.

Chapter 1

• Category theory is a tool for categorising mathematical objects
• “arrow” between objects in category theory is called morphism
• composition is binary operation for composing objects
  • this operation is associative
  • and has unit

Composition:

   

Asociativity (f, g, h are functions):

   

Unit:

   

• for every objects A, B, C from category theory, where f is morphism from A to B and g is morphism from B to C has to exist morphism g ○ f (from A to C)

Chapter 2

• type are intuitively sets of values (kind of) – they can be finite or infinite too (Bool vs Integer)
• mathematical function is relation between two values, it doesn’t describe steps to produce output from input

So the question is, do we want to make monkeys happy, or do we want to produce correct programs?

• example types in Haskell
  • Void – empty set
    • function with Void cannot be called. There is no way to provide no value
  • Unit – set with one value – empty tupple ()
    • can be used as parameter for constant function
  • Bool – set with two values (True and False)

absurd :: Void -> a

f44 :: () -> Integer
f44 () = 44

fInt :: Integer -> ()
fInt _ = ()

data Bool = True | False

Chapter 3

• categories examples
  • empty – without objects and morphisms
  • from graph
    • begin with directed graph
    • add identity morphism for each node
    • for each pair of edges (A, B) and (B, C), add (A, C)
    • repeat last step until no morphism can be added
    • thus we are creating category with object for every node of graph and morphism for every directed path
    • a category made from graph using these steps is called free category
  • orders
    • morphism in order is ≥ (relation between objects)
    • hom-set set of morphisms from a to b – C(a, b)
    • types
      • preorder – set with ≥ relation
        • at most one morphism from object a to object b = thin category
        • |C(a, b)| is 0 or 1
        • can contain cycle
      • partial order – if a ≥ b and b ≥ a, then a = b
        • can’t contain cycle
      • linear/total order – relation ≥ is defined for every pair of elements from set
    • common sorting algorithms can be used only on total order
    • partial order can be sorted using topological sort
  • monoids
    • monoid is set with binary operation
    • this operation is asociative and has unit
    • it doesn’t have to be commutative