# Category theory

(Difference between revisions)
Jump to: navigation, search
 Revision as of 16:59, 22 April 2008 (edit)m (typo)← Previous diff Revision as of 12:10, 28 July 2008 (edit) (undo) (Added information on the book _Categories and Computer Science,_ by R. F. C. Walters, and moved _Toposes, Triples and Theories,_ by Michael Barr and Charles Wells, to under the new "Books" subsection.)Next diff → Line 78: Line 78: * [http://www.eyrie.org/~zednenem/2004/hsce/ Category extras] by [http://www.eyrie.org/~zednenem/about/dave.html David Menendez]: libraries for e.g. comonads, infinite data types. * [http://www.eyrie.org/~zednenem/2004/hsce/ Category extras] by [http://www.eyrie.org/~zednenem/about/dave.html David Menendez]: libraries for e.g. comonads, infinite data types. + + ==Books== + + *Michael Barr and Charles Wells: [http://www.cwru.edu/artsci/math/wells/pub/ttt.html 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: [http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=0521419972 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. ==See also== ==See also== * Michael Barr and Charles Wells have a [http://www.math.upatras.gr/~cdrossos/Docs/B-W-LectureNotes.pdf paper] that presents category theory from a computer-science perspective, assuming no prior knowledge of categories. * Michael Barr and Charles Wells have a [http://www.math.upatras.gr/~cdrossos/Docs/B-W-LectureNotes.pdf paper] that presents category theory from a computer-science perspective, assuming no prior knowledge of categories. - *Michael Barr and Charles Wells: [http://www.cwru.edu/artsci/math/wells/pub/ttt.html 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''). *[http://wwwhome.cs.utwente.nl/~fokkinga/mmf92b.html A Gentle Introduction to Category Theory - the calculational approach] written by [http://wwwhome.cs.utwente.nl/~fokkinga/index.html Maarten M Fokkinga]. *[http://wwwhome.cs.utwente.nl/~fokkinga/mmf92b.html A Gentle Introduction to Category Theory - the calculational approach] written by [http://wwwhome.cs.utwente.nl/~fokkinga/index.html Maarten M Fokkinga]. * Wikipedia has a good [http://en.wikipedia.org/wiki/List_of_category_theory_topics collection of category-theory articles], although, as is typical of Wikipedia articles, they are rather dense. * Wikipedia has a good [http://en.wikipedia.org/wiki/List_of_category_theory_topics collection of category-theory articles], although, as is typical of Wikipedia articles, they are rather dense.

## Revision as of 12:10, 28 July 2008

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
. Various other Haskell structures can be used to make it a Cartesian closed category.

## Contents

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

## 1 Definition of a category

A category $\mathcal{C}$consists of two collections:

Ob$(\mathcal{C})$, the objects of $\mathcal{C}$

Ar$(\mathcal{C})$, the arrows of $\mathcal{C}$ (which are not the same as Arrows defined in GHC)

Each arrow f in Ar$(\mathcal{C})$ has a domain, dom f, and a codomain, cod f, each chosen from Ob$(\mathcal{C})$. The notation $f\colon A \to B$ means f is an arrow with domain A and codomain B. Further, there is a function $\circ$ called composition, such that $g \circ f$ is defined only when the codomain of f is the domain of g, and in this case, $g \circ f$ has the domain of f and the codomain of g.

In symbols, if $f\colon A \to B$ and $g\colon B \to C$, then $g \circ f \colon A \to C$.

Also, for each object A, there is an arrow $\mathrm{id}_A\colon A \to A$, (often simply denoted as 1 or id, when there is no chance of confusion).

### 1.1 Axioms

The following axioms must hold for $\mathcal{C}$ to be a category:

1. If $f\colon A \to B$ then $f \circ \mathrm{id}_A = \mathrm{id}_B\circ f = f$ (left and right identity)
2. If $f\colon A \to B$ and $g \colon B \to C$ and $h \colon C \to D$, then $h \circ (g \circ f) = (h \circ g) \circ f$ (associativity)

### 1.2 Examples of categories

• 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.
• 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)

### 1.3 Further definitions

With examples in Haskell at:

## 2 Categorical programming

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.

## 4 Books

• 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.