To understand $F$ -algebra, we will need some observations, the first one is we can summarize an algebra with a signature. For example, monoid has a signature:

\begin{cases} 1 : 1 \to m \\ \cdot : m \times m \to m \end{cases}

or we can say ring is:

\begin{cases} 0 : 1 \to m \\ 1 : 1 \to m \\ + : m \times m \to m \\ \times : m \times m \to m \\ - : m \to m \end{cases}

The next observation is we can consider these $m$ as objects in a proper category $C$ , at here is a [cartesian closed category](math-000D). For example

monoid is a $C$ -morphism $1 + m \times m \to m$
ring is a $C$ -morphism $1 + 1 + m \times m + m \times m + m \to m$

Now, we generalize algebra's definition.

Definition. $F$ -algebra (algebra for an endofunctor) [math-000F]

2023-10-24

With a proper category $C$ which can encode the signature of $F(-)$ , and an [endofunctor](math-001T) $F : C \to C$ , the $F$ -algebra is a triple:

(F, x, \alpha)

where $\alpha : F \; x \to x$ is a $C$ -morphism.

With the definition of $F$ -algebra, $F$ -algebras of a fixed $F$ form a category

Definition. category of $F$ -algebras [math-000G]

2023-10-24

For a fixed endofunctor $F$ in a proper category $C$ (below notations omit fixed $F$ ),

the F-algebras $(x, \alpha)$ form the objects of the category,
morphisms are homomorphisms of objects $(x, \alpha) \xrightarrow{F\;m} (y, \beta)$ , composition is given by functor laws.

A homomorphism is a $C$ -morphism $m$ makes below diagram commutes.

We can extra check identity indeed works.

There is a theorem about the initial object of the category.

Theorem. Lambek's [math-000H]

2023-10-24

The evaluator $j$ of an initial algebra $(F, i, j)$ is an isomorphism.

Proof

Let $F\;i$ be an initial in the $F$ -algebra category, the following diagram commutes for any $C$ -object $a$

Now, replace $a$ with $F\;i$ , we have commute diagram

Then we consider a trivial commute diagram by duplicating the path $F\;i \to i$

Combine two diagrams, then we get another commute diagram

By definition now we know $j \circ m$ is a homomorphism, and since $F\;i$ is an initial, we must have

F\;j \circ F\;m = 1_{Fi}

Therefore, we also have

j \circ m = 1_i

so $m$ is the inverse of $j$ , proves $j$ is an isomorphism.

catamorphism [math-000I]

2023-10-24

The theorem actually proves the corresponding $C$ -object $i$ of initial algebra $(F, i, j)$ is a fixed point of $F$ . By reversing $j$ with its inverse, we get a commute diagram below.

In Haskell, we are able to define initial algebra

newtype Fix f = Fix (f (Fix f))

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         unFix :: Fix f -> f (Fix f)
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         unFix (Fix x) = x

View $j$ as constructor Fix, $j^{-1}$ as unFix, then we can define m = alg . fmap m . unFix. Since m :: Fix f -> a, we have definition of catamorphism.

cata :: Functor f => (f a -> a) -> Fix f -> a
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         cata alg = alg . fmap (cata alg) . unFix

An usual example is foldr, a convenient specialization of catamorphism.

anamorphism [math-000J]

2023-10-24

As a dual concept, we can draw coalgebra diagram

and define anamorphism as well.

ana :: Functor f => (a -> f a) -> a -> Fix f
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         ana coalg = Fix . fmap (ana coalg) . coalg

I mostly learn F-algebras from Category Theory for Programmers, and take a while to express the core idea in details with my voice with a lot practicing. The article answered some questions, but we always with more. What's an algebra of monad? What's an algebra of a programming language (usually has a recursive syntax tree)? Hope you also understand it well through the article and practicing.