In mathematics, an initial algebra is an initial object in the category of F-algebras for a given endofunctor F.

Example

Consider the endofunctor $F:\; \backslash mathbf\{Set\}\; \backslash longrightarrow\; \backslash mathbf\{Set\}$ sending $X$ to $1+X$. Then the set $N$ of natural numbers together with the function $:\; 1+N\; \backslash longrightarrow\; N$, where $zero\; :\; 1\; \backslash longrightarrow\; N$ and $succ\; :\; N\; \backslash longrightarrow\; N$ are the obvious functions suggested by their names, is an initial $F$-algebra. The initiality (the universal property for this case) is not hard to establish; the unique homomorphism to an arbitrary F-algebra $(A,\; [e,f)$, for $e\; :\; 1\; \backslash longrightarrow\; A$ an element of A and $f\; :\; A\; \backslash longrightarrow\; A$ a function on A, is the function sending the natural number n to $f^n(e)$, that is, $f(f(...(f(e))...))$, the n-fold application of f to e.

Use in programming theory

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 $List(A)$ of lists whose elements are members of set A, consider that the list-forming operations are:

• $nil\; :\; 1\backslash longrightarrow\; List(A)$
• $cons\; :\; A\backslash times\; List(A)\backslash longrightarrow\; List(A)$

Combined into one function, they give:

• $*:\; 1\; +\; (A\backslash times\; List(A))\backslash longrightarrow\; List(A)$,

which makes this an F-algebra for the endofunctor F sending $X$ to $1+(A\backslash times\; X)$. It is, in fact, the initial F-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

• $*:\; A\; +\; (Tree(A)\backslash times\; Tree(A))\backslash longrightarrow\; Tree(A)$.

Types obtained this way are known as algebraic data types.

See also

• Algebraic data type
• Catamorphism

Category theory | Data structures | Functional programming