Category theory

Haskell theoretical foundations General: Mathematics - Category theory Research - Curry/Howard/Lambek Lambda calculus: Alpha conversion - Beta reduction Eta conversion - Lambda abstraction Other: Recursion - Combinatory logic Chaitin's construction - Turing machine Relational algebra

Category theory can be helpful in understanding Haskell's type system. There exists a "Haskell category", of which the objects are Haskell types, and the morphisms from types a to b are Haskell functions of type a -> b.

The Haskell wikibooks has an introduction to Category theory, written specifically with Haskell programmers in mind.

Definition of a category[edit]

A category Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{C}} consists of two collections:

ObFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathcal{C})} , the objects of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{C}}

ArFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathcal{C})} , the arrows of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{C}} (which are not the same as Arrows defined in GHC)

Each arrow Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} in ArFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathcal{C})} has a domain, dom Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} , and a codomain, cod Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} , each chosen from ObFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathcal{C})} . The notation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\colon A \to B} means Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} is an arrow with domain Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} and codomain Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} . Further, there is a function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \circ} called composition, such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g \circ f} is defined only when the codomain of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} is the domain of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} , and in this case, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g \circ f} has the domain of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} and the codomain of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g} .

In symbols, if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\colon A \to B} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g\colon B \to C} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g \circ f \colon A \to C} .

Also, for each object Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , there is an arrow Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{id}_A\colon A \to A} , (often simply denoted as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{id}} , when there is no chance of confusion).

Axioms[edit]

The following axioms must hold for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{C}} to be a category:

If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\colon A \to B} then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f \circ \mathrm{id}_A = \mathrm{id}_B\circ f = f} (left and right identity)
If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\colon A \to B} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g \colon B \to C} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h \colon C \to D} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h \circ (g \circ f) = (h \circ g) \circ f} (associativity)

Examples of categories[edit]

Set, the category of sets and set functions.
Mon, the category of monoids and monoid morphisms.
Monoids are themselves one-object categories.
Grp, the category of groups and group morphisms.
Rng, the category of rings and ring morphisms.
Grph, the category of graphs and graph morphisms.
Top, the category of topological spaces and continuous maps.
Preord, the category of preorders and order preserving maps.
CPO, the category of complete partial orders and continuous functions.
Cat, the category of categories and functors.

Hask
the category of data types and functions on data structures
the category of functions and data flows (~ data flow diagram)
the category of stateful objects and dependencies (~ object diagram)
the category of values and value constructors
the category of states and messages (~ state diagram)

Further definitions[edit]

With examples in Haskell at:

Categorical programming[edit]

Catamorphisms and related concepts, categorical approach to functional programming, categorical programming. Many materials cited here refer to category theory, so as an introduction to this discipline see the #See also section.

Erik Meijer, Maarten Fokkinga, Ross Paterson: Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. See also related documents (in the CiteSeer page). Understanding the article does not require knowledge of category theory—the paper is self-contained with regard to understanding catamorphisms, anamorphisms and other related concepts.
Roland Backhouse, Patrik Jansson, Johan Jeuring and Lambert Mertens. Generic Programming - an Introduction: Detailed introduction to categorial sums, product, polynomial functors and folds for the purpose of generic programming. Supplements the bananas paper.
Varmo Vene and Tarmo Uustalu: Functional Programming with Apomorphisms / Corecursion
Varmo Vene: Categorical Programming with Inductive and Coinductive Types. The book gives Haskell examples to illustrate the deep categorical theory topic.
Tatsuya Hagino: A Categorical Programming Language
Charity, a categorical programming language implementation.
Deeply uncurried products, as categorists might like them article mentions a conjecture: relatedness to Combinatory logic

Haskell libraries and tools[edit]

Originally, there was a package, Category extras, by David Menendez: libraries for e.g. functors, bifunctors, comonads, natural transformations, adjunctions and infinite data types. This package has been superseded by other more-focused and self-contained packages, as documented in the category-extras metapackage in Hackage. Almost all of them (e.g. comonad, bifunctors, categories, adjunctions, contravariant, free, profunctors, distributive, semigroupoids, kan-extensions, recursion-schemes) are done by Edward A. Kmett.

Notable other encoding of category theory is data-category by Sjoerd Visscher.

Books[edit]

Bartosz Milewski Category Theory for Programmers. Series of blog posts turned into a book. Covers many abstractions and constructions starting from basics: category, functor up to kan extensions, topos, enriched categories, F-algebras. There are video recordings with those content: part 1, part II and part III.

Michael Barr and Charles Wells: Toposes, Triples and Theories. The online, freely available book is both an introductory and a detailed description of category theory. It also contains a category-theoretical description of the concept of monad (but calling it a triple instead of monad).

R. F. C. Walters: Categories and Computer Science. Category Theory has, in recent years, become increasingly important and popular in computer science, and many universities now introduce Category Theory as part of the curriculum for undergraduate computer science students. Here, the theory is developed in a straightforward way, and is enriched with many examples from computer science.

Arbib&Manes: Arrow, Structures and Functors - The Categorical Imperative. (c)1975 Academic Press, ISBN 0-12-059060-3. Sadly now out of print but very little prerequisite knowledge is needed. It covers monads and the Yoneda lemma.

Brendan Fong, David I Spivak: Seven Sketches in Compositionality: An Invitation to Applied Category Theory. Different exposition to category theory focusing on applications in databases, circuits and signal flows.

Eugenia Cheng: The Joy of Abstraction. An introduction to category theory for anyone who wants to get into the formality of the subject but does not necessarily have the mathematical background to read a standard textbook.