Mathematical Induction
Associativity
Commutativity
Category Theory and Functional Programming
Objects and Elements
Category Theory and Structure
So what is category theory about? In every other aspect, either mathematics or physics or programming, we always look at the structure of things, right? In order to understand something, we want to decompose it and find what’s inside, right? It’s like you get a watch and you want to see like, how does it work? Why is it ticking, right? So you open it, you find the little parts, and then you decompose it into tiny little bits. Maybe you decompose it into atoms and then quartz, depending on how far you want to get to understand it. And category theory is very different from this. In category theory, you say I want to learn about this object, but I’m not going to look inside of this object at all. This object is black box. It’s a point. It has no structure. The structure of this object is given by how it interacts with other similar objects. So you always have a whole category of things. You want to talk about groups? Okay, what’s a category of groups? And in the category of groups, you don’t talk about what a group is like, what’s inside the group. No, you say, how is this group related to other groups, right? It’s more about understanding structure. I mean, it’s an amazing thing what category theory does, that it says, “Here’s a structure, it’s just objects and arrows. That’s it.” There’s nothing else. There’s just objects and arrows. And then you can study it and you can discover that these arrows can move in weird ways and combine in such crazy ways. And if you want to describe objects using just arrows, because arrows tell you how they interact with other objects, right? So there is a completely new way of talking about structure by saying how the arrows arrange themselves, right? And there is this stuff, for instance, called universal construction. Most of the things in category theory are defined using universal construction. A universal construction says, in order to understand this object, you have to tell me how it interacts with the whole universe, with every other object, not just a few objects, okay? No, with every object. That’s the universality of it, right? So this is so philosophical. You can’t be more philosophical than that, right? Make me whole with the universe, right? Bartosz Milewski, https://haskell.foundation/podcast/30/, 38:32
A set as a category with no structure
Composition, Application and Identity
Identity
Function application as function composition
Associativity of composition and its importance to problem-solving
Composition and problem-solving
Definition of function/morphism composition
Expression of composition in Haskell, where types and functions form a Category
Category Theory and other Mathematical Theories
Category theory as complementary to set theory
A set as a category with no structure
Category of Sets (Category of Types and Functions)
Modeling programming in the category of sets
An undercategory from the terminal object (coslice 1/C category) conveying set-theoretic types and functions
Category Theory and Thought Processes
Abstraction as discarding information in a function
Aris Goudouras
Not all functions perform abstraction (Milewski gives an example right after of injective functions / monomorphisms, which don’t abstract).
Morhpism/Function Types
Injective Functions / Monomorphisms
Surjective Functions / Epimorphisms
Bijective Functions / Isomorphisms
Isomorphism as the equivalent of object equality in Category Theory
Types
Sum Types
Bool
Enumerations
Either
Maybe
Functoriality/lifting for sum types
Introduction, elimination and computation rules
Product Types
Functoriality/lifting for products
Function Types
Function application as the elimination rule for function types
Functors
Functorial data types
Type constructors related to container & parameterized types
Important: type constructors not to be confused with arrows between objects
Functor as a kind of mapping that preserves structure
Functors must preserve identity arrows
Functors map objects but also arrows between them and therefore preserve structure
Functors must preserve composition
Endofunctors: functors that map a category to itself
Functoriality in Haskell (Functor type class and `fmap`)
Functoriality & Lifting
Type constructors: mapping types to other types
Composition and identity preservation with functors left to the programmer in Haskell
Types of Functors
Endofunctors: functors that map a category to itself
Bifunctors: functors that lift a pair of functions
Contravariant functors: functors lifting arrows that go in the opposite direction
Hom-Functor and Hom-Set
Important Categories for Programming
Category of Sets (Category of Types and Functions)
Modeling programming in the category of sets
An undercategory from the terminal object (coslice 1/C category) conveying set-theoretic types and functions
Opposite categories
Product categories of interest to programming
Endofunctors: functors that map a category to itself
Natural Transformations
Algebras
Goal: A general procedure for generating and manipulating arbitrary recursive types from simpler pluggable components