# F-algebra

In mathematics, specifically in category theory, an F-algebra is a structure defined according to a (endo-)functor F. F-algebras can be used to represent data structures used in programming, such as lists and trees. Initial F-algebras encapsulate an induction principle.

F-algebras are dual to F-coalgebras.

The commutative diagram, which defines a property required by morphisms of the original category, so that they can be morphisms of the newly defined category of F-algebras.

## Definition

If $\mathcal{C}$ is a category, and

$F : \mathcal{C}\longrightarrow \mathcal{C}$

is an endofunctor of $\mathcal{C}$, then an F-algebra is an object $A$ of $\mathcal{C}$ together with a $\mathcal{C}$-morphism

$\alpha : F(A) \longrightarrow A$.

In this sense F-algebras are dual to F-coalgebras.

A homomorphism from an F-algebra $(A, \alpha)$ to an F-algebra $(B, \beta)$ is a $\mathcal{C}$-morphism

$f:A\longrightarrow B$

such that

$f\circ \alpha = \beta \circ F(f)$,

see picture.

Thus the F-algebras constitute a category.

## Example

Consider the functor $F: \mathbf{Set} \to\mathbf{Set}$ that sends a set $X$ to $1+X$. Here, Set denotes the category of sets, $+$ denotes the usual coproduct given by disjoint union, and 1 is a terminal object (i.e. any singleton set). Then the set N of natural numbers together with the function $[\mathrm{zero},\mathrm{succ}] : 1+\mathbb{N} \to \mathbb{N}$, which is the coproduct of the functions $\mathrm{zero} : 1 \to \mathbb{N}$ (whose image is 0) and $\mathrm{succ} : \mathbb{N} \to \mathbb{N}$ (which sends an integer n to n+1), is an F-algebra.

## Initial F-algebra

Main article: Initial algebra

If the category of F-algebras for a given endofunctor F has an initial object, it is called an initial algebra. The algebra $(\mathbb{N}, [\mathrm{zero},\mathrm{succ}])$ in the above example is an initial algebra. Various finite data structures used in programming, such as lists and trees, can be obtained as initial algebras of specific endofunctors.

Types defined by using least fixed point construct with functor F can be regarded as an initial F-algebra, provided that parametricity holds for the type.[1]