F-algebra

- #category_theory

F-algebra，也叫 functor algebra，是 algebra 在 category 里的一个版本。

给定一个 endofunctor：

F : C \to C

一个 F-algebra 是一对：

(A, \alpha)

其中：

- A 是 carrier，也就是 category C 里的一个 object

- \alpha : F(A) \to A 是 operation

所以 F-algebra 的基本形式是：

\text{F-algebra} = \text{carrier } A + \text{operation } \alpha : F(A) \to A

这里的重点是：F 不是 algebra 本身。F 的作用是描述 operation 的输入形状。真正的 algebra 是 (A, \alpha)。

普通 algebra 里，operation 的形状通常直接写出来。例如一个 binary operation：

A \times A \to A

在 F-algebra 里，可以先用 functor 描述这个输入形状：

F(X) = X \times X

那么一个 F-algebra 就是：

\alpha : F(A) \to A

展开后就是：

\alpha : A \times A \to A

也就是在 carrier A 上给出一个二元 operation。

如果定义：

F(X) = 1 + X \times X

那么一个 F-algebra：

\alpha : 1 + A \times A \to A

等价于给出：

- 一个 nullary operation，也就是一个 constant/unit: 1 \to A

- 一个 binary operation: A \times A \to A

所以可以把 F-algebra 理解成：functor F 先规定 operation 的输入形状，然后 \alpha 在某个 carrier A 上实现这些 operation。

F-algebra 也是一种 algebra，只是它把 operation signature 用 functor 打包成了一个输入：

F(A)

相关：algebra、functor、endofunctor、category