始代数
リストや木構造など、プログラミングで使われる有限データ構造の多くは、特定の関手に対する始代数として構成することができる。与えられた自己関手に対応する始代数は複数存在し得るけれども、それらは同型の違いを除いて一意である。このことはつまり直感的には、データ構造が「持っているはず」の性質はデータ構造を始代数として定義することで適切に(実現の仕方に依らないで)捕捉できるということである。
集合 A の元を要素に持つリストのデータ型 L i s t ( A ) {\displaystyle \mathrm {List} (A)} を得るために、リスト構成演算
n i l : 1 → L i s t ( A ) , {\displaystyle \mathrm {nil} \colon 1\to \mathrm {List} (A),}
c o n s : A × L i s t ( A ) → L i s t ( A ) {\displaystyle \mathrm {cons} \colon A\times \mathrm {List} (A)\to \mathrm {List} (A)}
の直和として与えられる一つの関数
[ n i l , c o n s ] : 1 + ( A × L i s t ( A ) ) → L i s t ( A ) {\displaystyle [\mathrm {nil} ,\mathrm {cons} ]\colon 1+(A\times \mathrm {List} (A))\to \mathrm {List} (A)}