「Catamorphism」の版間の差分

編集の要約なし
(新しいページ: '圏論において、'''Catamorphism'''(ギリシャ語: κατά = ''下方へ'' または ''~に従って''; [[wikt:μορφή|μ...')
 
[[圏論]]において、'''Catamorphism'''([[ギリシャ語]]: [[wikt:κατά|κατά]] = ''下方へ'' または ''~に従って''; [[wikt:μορφή|μορφή]] = ''形式'' または ''形'')は、[[始代数]]から他のいくつかの[[F代数|代数]]への[[F代数#形式的定義|準同型射]]を意味する概念である。この概念は[[関数型プログラミング]]の[[モノイド#計算機科学におけるモノイド|fold]]に適用されている。
 
[[anamorphismAnamorphism]]はこの双対となる概念である。[[Hylomorphism]]も参照。
 
== 関数型プログラミングにおけるCatamorphism ==
 
関数型プログラミングでは、'''catamorphismCatamorphism'''は[[リスト_(抽象データ型)|リスト]]の[[モノイド#計算機科学におけるモノイド|fold]]として知られる始代数を、任意の[[代数的データ型]]で記述できるように一般化したものである。
 
プログラミングにおいてcatamorphismCatamorphismの概念を導入した最初の出版物の一つは、“Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire”, by [[Erik Meijer (computer scientist)|Erik Meijer]] ''et al.''[http://citeseer.ist.psu.edu/meijer91functional.html]で、[[Bird-Meertens formalism]]の文脈であった。
 
[[双対]]である[[Anamorphism]]は、''unfold''の一般化である。
そのような関手''F''上の''F''-代数の圏で、始代数が存在すれば、<code>Tree</code>、またはHaskellの項、<code>(Tree a, [Leaf, Branch])</code>で表現する。
 
<code>Tree a</code> は''F''-代数の圏の[[始対象]]であり、<code>Tree a</code>から任意の''F''-代数へ一意な準同型射を与える。この一意な準同型射は''catamorphismCatamorphism''と呼ばれる。
 
=== 一般的な場合 ===
 
[[圏論]]では、catamorphismはCatamorphismと[[anamorphismAnamorphism]][[圏論的双対]]である。(そしてanamorphismはcatamorphismの圏論的双対でもある)
 
この意味は次の通り。
 
=== 記法 ===
cata ''f'' は別の記法 <math>(\!|f|\!)</math> と記されることがある。使用されている開いた括弧は「'''バナナ括弧'''」として知られ、{{Harvnb|Meijer|1991}}などで記載された後は、catamorphismCatamorphismは時に「バナナ」と呼ばれる。
 
== 関連項目 ==
310

回編集