F代数

圏 C とその上の自己関手 F: C → C に対し、F-代数とは C の対象 A と C の射 α: F(A) → A との組 (A, α) のことをいう。この意味で、F-代数は F-余代数の双対である。

F-代数 (A, α) から別の F-代数 (B, β) への F-代数の準同型とは、C-射 f: A → B で条件 $${\displaystyle f\circ \alpha =\beta \circ F(f)}$$ を満たす（すなわち、右図の図式を可換にする）ものをいう。

F-代数の全体は、F-代数準同型を射として圏をなす。

Set を集合の圏、1 を Set における終対象（すなわち任意の一元集合）、+ は Set における（圏論的）直和（すなわち非交和）とするとき、Set の自己函手 F: X → 1 + X を考えると、(N, [0, succ]) は一つの F-代数を与える。ただし、N は自然数全体の成す集合、[0,succ] は二つの写像 $${\displaystyle 0\colon 1\to \mathbb {N}$$ ;*\mapsto 0,} $${\displaystyle \mathrm {succ} \colon \mathbb {N} \to \mathbb {N} ;n\mapsto n+1}$$ の直和（つまり、x ∈ 1 + N が x ∈ 1 ならば写像 0 に x ∈ N ならば写像 succ に一致するような写像）である。

与えられた自己函手 F に対する F-代数の圏が始対象を持つならば、その始対象を F-始代数と呼ぶ。上記の例で挙げた代数 (N, [0,succ]) は始代数である。プログラミングで使われるリストや木構造のようないくつもの有限データ構造が、特定の自己関手の始代数として得られる。

函手 F から構成した最小不動点で定義される型は F-始代数と見なすことができ、これはこの型に対するパラメトリシティ(en:parametricity)を保つものとしてよい。^[1]

双対的な方法で、同様の関係が最大不動点とF-終余代数の間に存在する。これらは強正規化性を維持しながら、可能無限個のオブジェクトを扱うことを可能にする。^[1] 強正規化を行うプログラミング言語Charityの、余帰納的データ型は驚くべき結果を得ることが出来る。 例えば、アッカーマン関数のような"強い"関数を実装するために参照の構成要素を定義する。^[2]