F代数とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > F代数の意味・解説 

F代数

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/10/11 15:51 UTC 版)

数学の特に圏論におけるF-代数(エフだいすう、: F-algebra)は、(自己)関手 F に従って定義される構造の一つで、リスト木構造のようなプログラミングで使われるデータ構造を表現するのに利用できる。 F-始代数は、数学的帰納法の原理を捉えたものと考えることができる。文脈上紛れの虞が無い場合は、函手 F を明示するための接頭辞 F- を省略して単に代数ということがある。

F-代数は F-余代数双対である。

厳密な定義

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

F-代数の準同型がもとの圏において満たすべき条件を示した可換図式。すなわち、この条件を満たす f が新しい F-代数の圏での射となる。

F-代数 (A, α) から別の F-代数 (B, β) への F-代数の準同型とは、C-射 f: AB で条件

を満たす(すなわち、右図の図式を可換にする)ものをいう。

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

Set集合の圏、1 を Set における終対象(すなわち任意の一元集合)、+ は Set における(圏論的)直和(すなわち非交和)とするとき、Set の自己函手 F: X → 1 + X を考えると、(N, [0, succ]) は一つの F-代数を与える。ただし、N自然数全体の成す集合、[0,succ] は二つの写像

の直和(つまり、x ∈ 1 + Nx ∈ 1 ならば写像 0 に xN ならば写像 succ に一致するような写像)である。

F -始代数

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

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

F -終余代数

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

脚注

  1. ^ a b Philip Wadler: Recursive types for free! University of Glasgow, July 1998. Draft.
  2. ^ Robin Cockett: Charitable Thoughts (ps and ps.gz)

参考文献

  • Pierce, Benjamin C.. “F-Algebras”. Basic Category Theory for Computer Scientists. ISBN 0262660717 

関連項目

外部リンク




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「F代数」の関連用語

F代数のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



F代数のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのF代数 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS