REVISED: Wednesday, January 24, 2024
Haskell Category Theory.
I. HASKELL "CATEGORY THEORY"
Category theory first appeared in a paper entitled "General Theory of Natural Equivalences", written by Samuel Eilenberg and Saunders Mac Lane in 1945.
The focus of category theory is on composition. A category is just a bunch of objects A, B, C... and some processes f, g, h...
There is one different identity process for each of the objects A, B, C... ; therefore, category theory is not polymorphic.
In set theory, morphisms are functions; however in category theory morphisms is a broadly similar idea, but somewhat more abstract: the mathematical objects involved need not be sets, and the relationship between them may be something more general than a map.
Category theory is a powerful tool for studying similarities. For example, generalizing set definitions for one-to-one and onto functions to category theory as shown below.
A. MONOMORPHISM
. read "of"; e.g, f of g, f.g is a function, such that (f.g)(x) = f(g(x)). The notation f o g means that we apply g first and then f.
Morphism is read "function".
A function f from A to B is called one-to-one if, whenever f (a) = f (b), then a = b. No element of B is the image of more than one element in A.
In mathematics, an image is the subset of a function's codomain which is the output of the function on a subset of its domain. In other words, it can be thought of as a subobject, an object which sits inside another object in the same category. Therefore, a monic process defines a subobject.
What can go into a function is called the domain.
What may possibly come out of a function is called the codomain.
What actually comes out of a function is called the range.
For a one-to-one function f, for each g and h, if f.g = f.h then g = h and f is monic.
The monic process (monomorphism), also called a monic morphism or a mono, is a left-cancellative morphism. Which means a monic process can be canceled out on the left.
B. EPIMORPHISM
A function f from A to B is called onto if for all b in B there is an a in A such that f (a) = b. All elements in B are used.
For an onto function f, for each g and h, if g.f = h.f then g = h and f is epic.
An epic process (epimorphism) is a right-cancellative morphism. Which means an epic process can be canceled out on the right.
C. ISOMORPHISM
: read "such that".
→ read "maps set" A into set B.
An iso process (isomorphism) is not an epic and monic process.
Let C be a category, and let X, Y be objects of C.
A morphism f:X→Y is an isomorphism if there exists a morphism g:Y→X such that:
g.f = idX
f.g = idY
where idX denotes the identity morphism on X.
II. INITIAL OBJECT
An initial object I is one from which there is one arrow from I to any other object. That kind of object is playing the role of the empty set. There is no initial object in the category of Haskell programs since any type is inhabited by undefined.
Given
∀ read "for every".
∈ read "is an element of".
• read "is a function of".
∃! read "there exists exactly one".
: read "such that".
→ read "maps set X into set T".
Then let C be a category.
A terminal object in C is an object T. T is playing a similar role to the singleton set.
T ∈ C : ∀ X ∈ C ∃! morphism X → T
IV. CATEGORY
A Category is a collection of objects and arrows. Arrows are called “morphisms” in Category Theory. An arrow points from a source object to a destination object. Arrows are relationships or functions. If you think of arrows as relationships an arrow could be a relationship like “greater than or equal”. If you think of arrows as functions, then the initial source object is the input to the function and the terminal output object is the output of the function.
V. CONCLUSION
In this tutorial, you have received an introduction to Haskell "Category Theory".
Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.
Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.
Goerzen, J. & O'Sullivan, B. & Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.
Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.
Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.
Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.
