Free

Category Theory for Programmers

By Bartosz Milewski

Free

Read Now

Description Table of Contents Reviews

Book Description

For some time now I’ve been oating the idea of writing a book about category theory that would be targeted at programmers. Mind you, not computer scientists but pro- grammers — engineers rather than scientists. I know this sounds crazy and I am properly scared. I can’t deny that there is a huge gap between science and engineering be- cause I have worked on both sides of the divide. But I’ve al- ways felt a very strong compulsion to explain things. I have tremendous admiration for Richard Feynman who was the master of simple explanations. I know I’m no Feynman, but I will try my best. I’m starting by publishing this pref- ace — which is supposed to motivate the reader to learn category theory — in hopes of starting a discussion and soliciting feedback.

This is an unofficial PDF version of "Category Theory for Programmers" by Bartosz Milewski, converted from his blogpost series.

Table of Contents

Preface
I Part One
- Category: The Essence of Composition
  - Arrows as Functions
  - Properties of Composition
  - Composition is the Essence of Programming
  - Challenges
- Types and Functions
  - Who Needs Types?
  - Types Are About Composability
  - What Are Types?
  - Why Do We Need a Mathematical Model?
  - Pure and Dirty Functions
  - Examples of Types
  - Challenges
- Categories Great and Small
  - No Objects
  - Simple Graphs
  - Orders
  - Monoid as Set
  - Monoid as Category
  - Challenges
- Kleisli Categories
  - The Writer Category
  - Writer in Haskell
  - Kleisli Categories
  - Challenge
- Products and Coproducts
  - Initial Object
  - Terminal Object
  - Duality
  - Isomorphisms
  - Products
  - Coproduct
  - Asymmetry
  - Challenges
  - Bibliography
- Simple Algebraic Data Types
  - Product Types
  - Records
  - Sum Types
  - Algebra of Types
  - Challenges
- Functors
  - Functors in Programming
    - The Maybe Functor
    - Equational Reasoning
    - Optional
    - Typeclasses
    - Functor in C++
    - The List Functor
    - The Reader Functor
  - Functors as Containers
  - Functor Composition
  - Challenges
- Functoriality
  - Bifunctors
  - Product and Coproduct Bifunctors
  - Functorial Algebraic Data Types
  - Functors in C++
  - The Writer Functor
  - Covariant and Contravariant Functors
  - Profunctors
  - Challenges
- Function Types
  - Universal Construction
  - Currying
  - Exponentials
  - Cartesian Closed Categories
  - Exponentials and Algebraic Data Types
    - Zeroth Power
    - Powers of One
    - First Power
    - Exponentials of Sums
    - Exponentials of Exponentials
    - Exponentials over Products
  - Curry-Howard Isomorphism
  - Bibliography
- Natural Transformations
  - Polymorphic Functions
  - Beyond Naturality
  - Functor Category
  - 2-Categories
  - Conclusion
  - Challenges
II Part Two
- Declarative Programming
- Limits and Colimits
  - Limit as a Natural Isomorphism
  - Examples of Limits
  - Colimits
  - Continuity
  - Challenges
- Free Monoids
  - Free Monoid in Haskell
  - Free Monoid Universal Construction
  - Challenges
- Representable Functors
  - The Hom Functor
  - Representable Functors
  - Challenges
  - Bibliography
- The Yoneda Lemma
  - Yoneda in Haskell
  - Co-Yoneda
  - Challenges
  - Bibliography
- Yoneda Embedding
  - The Embedding
  - Application to Haskell
  - Preorder Example
  - Naturality
  - Challenges
III Part Three
- It's All About Morphisms
  - Functors
  - Commuting Diagrams
  - Natural Transformations
  - Natural Isomorphisms
  - Hom-Sets
  - Hom-Set Isomorphisms
  - Asymmetry of Hom-Sets
  - Challenges
- Adjunctions
  - Adjunction and Unit/Counit Pair
  - Adjunctions and Hom-Sets
  - Product from Adjunction
  - Exponential from Adjunction
  - Challenges
- Free/Forgetful Adjunctions
  - Some Intuitions
  - Challenges
- Monads: Programmer's Definition
  - The Kleisli Category
  - Fish Anatomy
  - The do Notation
- Monads and Effects
  - The Problem
  - The Solution
    - Partiality
    - Nondeterminism
    - Read-Only State
    - Write-Only State
    - State
    - Exceptions
    - Continuations
    - Interactive Input
    - Interactive Output
  - Conclusion
- Monads Categorically
  - Monoidal Categories
  - Monoid in a Monoidal Category
  - Monads as Monoids
  - Monads from Adjunctions
- Comonads
  - Programming with Comonads
  - The Product Comonad
  - Dissecting the Composition
  - The Stream Comonad
  - Comonad Categorically
  - The Store Comonad
  - Challenges
- F-Algebras
  - Recursion
  - Category of F-Algebras
  - Natural Numbers
  - Catamorphisms
  - Folds
  - Coalgebras
  - Challenges
- Algebras for Monads
  - T-algebras
  - The Kleisli Category
  - Coalgebras for Comonads
  - Lenses
  - Challenges
- Ends and Coends
  - Dinatural Transformations
  - Ends
  - Ends as Equalizers
  - Natural Transformations as Ends
  - Coends
  - Ninja Yoneda Lemma
  - Profunctor Composition
- Kan Extensions
  - Right Kan Extension
  - Kan Extension as Adjunction
  - Left Kan Extension
  - Kan Extensions as Ends
  - Kan Extensions in Haskell
  - Free Functor
- Enriched Categories
  - Why Monoidal Category?
  - Monoidal Category
  - Enriched Category
  - Preorders
  - Metric Spaces
  - Enriched Functors
  - Self Enrichment
  - Relation to 2-Categories
- Topoi
  - Subobject Classifier
  - Topos
  - Topoi and Logic
  - Challenges
- Lawvere Theories
  - Universal Algebra
  - Lavwere Theories
  - Models of Lawvere Theories
  - The Theory of Monoids
  - Lawvere Theories and Monads
  - Monads as Coends
  - Lawvere Theory of Side Effects
  - Challenges
  - Further Reading
- Monads, Monoids, and Categories
  - Bicategories
  - Monads
  - Challenges
  - Bibliography
- Acknowledgments
- Index
- Colophon
- Copyleft notice