「Catamorphism」の版間の差分

後半の訳を修正
(前半の訳を修正)
(後半の訳を修正)
== [[圏論]]におけるCatamorphisms ==
 
[[圏論]]は、全ての基礎的なデータ型を記述する一般的な定義を与えるため必要不可欠な概念を提供する(関数型プログラミングではにおける関数を識別するのに[[圏|集合の圏]]や関連した具体的な圏の[[射_(圏論)|射]]が使われ、[[圏|集合の圏]]または、いくつかの関連と同一視するによっ構成する)。これはGrant Malcolmによって行われた。<ref>{{Citation |last=Malcolm |first=Grant |year=1990 |title=Algebraic types and program transformation |format=Ph.D. Thesis |publisher=University of Groningen}}.</ref><ref>{{Citation |last=Malcolm |first=Grant |year=1990 |title=Data structures and program transformation |periodical=Science of Computer Programming |volume=14 |issue=2-3 |pages=255–279 |doi=10.1016/0167-6423(90)90023-7}}.</ref>.
 
上記の例に戻り、<code>r</code>から<code>a + r &times; r</code>を対応させる関手''F''を考える。
この特殊な定の場合に対応する[[F代数]]のために、組(<code>r</code>, <nowiki>[</nowiki><code>f1</code>,<code>f2</code><nowiki>]</nowiki>)である、ここで<code>r</code> は対象でありそして二つの射 <code>f1</code> と <code>f2</code> は
:<code>f1: a &rarr; r</code>
:<code>f2: r &times; r &rarr; r</code>
として定義される。
 
ような関手''F''上のにおける''F''-代数の圏の場合、始代数存在すれば、<code>Tree</code>、またを表現する。これはHaskellの用語で言えば、<code>(Tree a, [Leaf, Branch])</code>で表現する。
 
<code>Tree a</code> は''F''-代数の圏の[[始対象]]であることにより、<code>Tree a</code>から任意の''F''-代数へ一意な準同型射を与える。この一意な準同型射は''Catamorphism''と呼ばれる。
 
=== 一般的な場合 ===
 
[[圏論]]では、Catamorphismと[[Anamorphism]]は[[圏論的双対]]である。
 
これは以下を意味する。(''A'', ''in'')をある圏からそれ自身への自己関手''F'に対する[[始代数]]とする。
この意味は次の通り。
従って、''in''は''FA''から''A''への射であり、これが始であると仮定したので、つまり、(''X'', ''f'')を他のF-代数(射''f'' : ''FX'' &rarr; ''X''のこと)とすると、(''A'', ''in'')から(''X'', ''f'')への一意な準同型射''h''が常に存在すると仮定したので、''A''から''X''への射''h''で、''h '''.''' in = f '''.''' Fh''を満たすものもまた存在する。
そして、各''f''に対して一意に指定された射''h''を'''cata''' '''''f'''''で表す。
 
言い換えれば、上記はいくつかの固定された''F''、''A''、''in''に対して、以下の関係式によって与えられる次の定義の関係を持つすることもできる
(''A'', ''in'')はそれ自体、いくつかの圏のいくつかの自己関手''F''の[[始代数]]と仮定する。
従って、''in''は''FA''から''A''への射で、他のF-代数(''X'', ''f'')の始対象であると仮定できる。(射''f''は''f'' : ''X'' &rarr; ''Y'')
 
(''A'', ''in'')から(''X'', ''f'')への一意な準同型射''h''があり、''h''は''h '''.''' in = f '''.''' Fh''であるような''h'' : ''A'' &rarr; ''X''。
よって、このような''f''は'''cata''' '''''f'''''で一意に指定された射''h''によって表す。
 
言い換えれば、上記はいくつかの固定された''F''、''A''、''in''によって与えられる次の定義の関係を持つ。
 
*<math>h = \mathrm{cata}\ f</math>
匿名利用者