# F-Algebras

## Definition

Let $$F: \mathcal{C}\rightarrow \mathcal{C}$$ be a endofunctor. An F-Algebra is a pair $$(A,\alpha)$$ where $$A$$ is an object of $$\mathcal{C}$$ and $$\alpha : F(A)\rightarrow A$$ is a morphism of $$\mathcal{C}$$.

So F-algebra is just a function from an endofunctor to an object, or rather the pair of a object and a function from it -- lifted to the functor -- to itself.

Let's try and apply this concept, we're going to construct a multiplication algebra. For this we define our endofunctor as $$F: A\mapsto A\times A$$. So the functor maps a given set to it's squared set i.e. $$\mathbb{N}$$ would be mapped to $$\mathbb{N}\times\mathbb{N}$$. On a squared set like this the multiplication is defined $$\alpha: \mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$$ as follows $$\alpha:x,y\mapsto x*y$$. The resulting algebra would then be noted as $$(\mathbb{N}, *)$$.

### Operating on F-algebras

F-algebras can be mapped onto one another, this happens for a given functor $$F$$ inside the category $$Alg(F)$$. Inside this category the objects are the F-algebras $$(A,\alpha)$$ and the homomorphisms $$h: (A,\alpha)\rightarrow(B,\beta)$$ the morphisms.

We will see when dealing with catamorphisms, that we can construct a F-algebra-homomorphism under $$F: A \rightarrow 1 + \mathbb{N}\times A$$ from the F-algebra of lists $$(\mathbb{L}, [I_{[]}, +])$$ (with $$+$$ being the function that concatenates two lists) to the F-algebra of Numbers and their products $$(\mathbb{N},[I_1, *])$$. This homomorphism represents the multiplicative combination (or product) of the list-elements.

## F-co-algebras

Let $$F: \mathcal{C}\rightarrow \mathcal{C}$$ be a endofunctor. An F-co-algebra is a pair $$(A,\alpha)$$ where $$A$$ is an object of $$\mathcal{C}$$ and $$\alpha : A\rightarrow F(A)$$ is a morphism of $$\mathcal{C}$$.

That means that, if $$(A,\alpha)$$ is an F-algebra, $$(A,\alpha^{-1})$$ is an F-co-algebra if the functions inverse $$\alpha^{-1}$$ exists.

## Initial F-algebra

An F-algebra $$(A,\alpha)$$ is called initial if for every F-algebra $$(B,\beta)$$ in the category $$Alg(F)$$ there exists exactly one morphism $$h: (A,\alpha)\rightarrow(B,\beta)$$.

The F-algebra of lists is an example of an initial F-algebra, this tells us that we can do basically anything with a list of objects, where 'do anything' means that there is a morphism for all these operations.

## Final F-algebra

An F-algebra $$(B,\beta)$$ is called final if for every F-algebra $$(A,\alpha)$$ in the category $$Alg(F)$$ there exists exactly one morphism $$h: (A,\alpha)\rightarrow(B,\beta)$$.

## F-algebra-homomorphism

Let $$\mathcal{C}$$ be a category and $$F:\mathcal{C}\rightarrow\mathcal{C}$$ an endofunctor. A morphism is exactly then a F-algebra-homomorphism if the following diagram commutates

The following equation can be read from the diagram:

$$h\circ \alpha = \beta\circ F(h)$$

## Preview

In the next article we'll finally get down to real business and look at recursive collapse using catamorphisms.