「Catamorphism」の版間の差分

m
タグ: モバイル編集 モバイルウェブ編集 改良版モバイル編集
タグ: モバイル編集 モバイルウェブ編集 改良版モバイル編集
 
[[Anamorphism]]はこの双対となる概念である。[[Hylomorphism]]も参照。
 
== 関数型プログラミングにおける Catamorphism ==
 
'''Catamorphism'''は関数型プログラミングにおいて[[リスト_(抽象データ型)|リスト]]の [[モノイド#計算機科学におけるモノイド|fold]] と呼ばれる操作を、[[始代数]]として表現できる任意の[[代数的データ型]]に一般化したものである。
 
プログラミングにおいて Catamorphism の概念を導入した最初の出版物の一つは、“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'' の一般化である。
[[Hylomorphism]]は、Anamorphism Catamorphism の合成、つまりまず Anamorphism を適用し次に Catamorphism を適用するものである。
 
=== 例 ===
次の例は [[Haskell]] によるもの。
 
<sourcesyntaxhighlight lang="haskell">
data Tree a = Leaf a
| Branch (Tree a) (Tree a)
sumTree :: (Num a) => TreeAlgebra a a
sumTree = (id, (+))
</syntaxhighlight>
</source>
 
 
ここで、<code>foldTree (''f'', ''g'')</code> は[[抽象データ型|データ型]]<code>Tree ''a''</code> の'' catamorphism'' で、 <code>treeDepth</code> と<code>sumTree</code> は''代数''と呼ばれる。
 
== 圏論における Catamorphism ==