Catamorphisms in Category Theory
Category theory provides the necessary concepts to give a generic definition that accounts for all initial data types (using an identification of functions in functional programming with the morphisms of the category Set or some related concrete category). This was done by Grant Malcolm.
Returning to the above example, consider a functor F sending r
to a + r × r
. An F-algebra for this specific case is a pair (r
, ), where r
is an object, and f1
and f2
are two morphisms defined as f1: a → r
, and f2: r × r → r
.
In the category of F-algebras over such F, an initial algebra, if it exists, represents a Tree
, or, in Haskell terms, it is (Tree a, )
.
Tree a
being an initial object in the category of F-algebras, there is a unique homomorphism of F-algebras from Tree a
to any given F-algebra. This unique homomorphism is called catamorphism.
Read more about this topic: Catamorphism
Famous quotes containing the words category and/or theory:
“The truth is, no matter how trying they become, babies two and under dont have the ability to make moral choices, so they cant be bad. That category only exists in the adult mind.”
—Anne Cassidy (20th century)
“The weakness of the man who, when his theory works out into a flagrant contradiction of the facts, concludes So much the worse for the facts: let them be altered, instead of So much the worse for my theory.”
—George Bernard Shaw (18561950)