計算機科学での利用
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2013/12/28 13:32 UTC 版)
リストや木構造など、プログラミングで使われる有限データ構造の多くは、特定の関手に対する始代数として構成することができる。与えられた自己関手に対応する始代数は複数存在し得るけれども、それらは同型の違いを除いて一意である。このことはつまり直感的には、データ構造が「持っているはず」の性質はデータ構造を始代数として定義することで適切に（実現の仕方に依らないで）捕捉できるということである。 集合 A の元を要素に持つリストのデータ型 を得るために、リスト構成演算 の直和として与えられる一つの関数 が A を台集合として、X に 1 + (A × X) を対応させる Set の自己函手 F に対する F-代数を与えることを注意しよう。実はこれが唯一の F-始代数となる。この始代数が持つ始対象性は、HaskellやMLのような関数型プログラミング言語でfoldrと呼ばれている関数によって与えられる。 同様に、葉に要素を持つ二分木は、 の与える始代数として得ることができる。この方法で得られるデータ型を代数的データ型と呼ぶ。 函手 F から構成される最小不動点を用いて定義されたデータ型は、 F-代数と見なすことができ、またこのデータ型がパラメトリシティ（英語版）を持つようにすることができる。双対に移って、最大不動点と F-終余代数の間に同様の関係が成立し、余帰納的データ型に応用される。これらを、強正規化性を維持しながら可能無限のオブジェクトを扱うことを許すために用いることができる。強正規化を行うプログラミング言語Charityの、余帰納的データ型は驚くべき結果を得ることが出来る。 例えば、アッカーマン関数のような"強い"関数を実装するために参照の構成要素を定義する。
※この「計算機科学での利用」の解説は、「始代数」の解説の一部です。
「計算機科学での利用」を含む「始代数」の記事については、「始代数」の概要を参照ください。
- 計算機科学での利用のページへのリンク
