Consider the endofunctor sending to, where is the one-point set, the terminal object in the category. An algebra for this endofunctor is a set together with a function. Defining such a function amounts to defining a point and a function. Define and Then the set of natural numbers together with the function is an initial -algebra. The initiality is not hard to establish; the uniquehomomorphism to an arbitrary -algebra, for an element of and a function on, is the function sending the natural number to, that is,, the -fold application of to. The set of natural numbers is the carrier of an initial algebra for this functor: the point is zero and the function is the successor function.
Functor
For a second example, consider the endofunctor on the category of sets, where is the set of natural numbers. An algebra for this endofunctor is a set. To define such a function, we need a point and a function. The set of finite lists of natural numbers is an initial algebra for this functor. The point is the empty list, and the function is cons, taking a number and a finite list, and returning a new finite list with the number at the head. In categories with binary coproducts, the definitions just given are equivalent to the usual definitions of a natural number object and a list object, respectively.
Final coalgebra
, a final coalgebra is a terminal object in the category of -coalgebras. The finality provides a general framework for coinduction and corecursion. For example, using the same functor as before, a coalgebra is defined as a set together with a function. Defining such a function amounts to defining a partial function whose domain is formed by those for which belongs to. Such a structure can be viewed as a chain of sets, on which is not defined, which elements map into by, which elements map into by, etc., and containing the remaining elements of. With this in view, the set consisting of the set of natural numbers extended with a new element is the carrier of the final coalgebra in the category, where is the predecessor function on the positive naturals, but acts like the identity on the new element :,. This set that is the carrier of the final coalgebra of is known as the set of conatural numbers. For a second example, consider the same functor as before. In this case the carrier of the final coalgebra consists of all lists of natural numbers, finite as well as infinite. The operations are a test function testing whether a list is empty, and a deconstruction function defined on non-empty lists returning a pair consisting of the head and the tail of the input list.
Various finite data structures used in programming, such as lists and trees, can be obtained as initial algebras of specific endofunctors. While there may be several initial algebras for a given endofunctor, they are unique up to isomorphism, which informally means that the "observable" properties of a data structure can be adequately captured by defining it as an initial algebra. To obtain the type of lists whose elements are members of set, consider that the list-forming operations are: Combined into one function, they give:
,
which makes this an -algebra for the endofunctor sending to. It is, in fact, the initial -algebra. Initiality is established by the function known as foldr in functional programming languages such as Haskell and ML. Likewise, binary trees with elements at the leaves can be obtained as the initial algebra
