Catamorphism
↑ Malcolm, Grant (1990) (Ph.D. Thesis), Algebraic types and program transformation, University of Groningen .
↑ Malcolm, Grant (1990), “Data structures and program transformation”, Science of Computer Programming 14 (2-3): 255–279, doi:10.1016/0167-6423(90)90023-7 .
Catamorphismは関数型プログラミングにおいてリストの fold と呼ばれる操作を、始代数として表現できる任意の代数的データ型に一般化したものである。
プログラミングにおいて Catamorphism の概念を導入した最初の出版物の一つは、“Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire”, by Erik Meijer et al.で、Bird-Meertens formalismの文脈であった。
双対である Anamorphism は、unfold の一般化である。 Hylomorphismは、Anamorphism と Catamorphism の合成、つまりまず Anamorphism を適用し次に Catamorphism を適用するものである。
圏論は、全ての始データ型を記述する一般的な定義を与えるために必要な概念を提供する(関数型プログラミングにおける関数を集合の圏や関連した具体的な圏の射と同一視することによって)。これはGrant Malcolmによって行われた。.
上記の例に戻り、rにa + r × rを対応させる関手Fを考える。 この特定の場合に対応するF代数は組(r, [f1,f2])である、ここでr は対象であり、二つの射 f1 と f2 は
f1: a → r
f2: r × r → r
として定義される。
この関手FにおけるF-代数の圏の場合、始代数は存在すれば、Treeを表現する。これはHaskellの用語で言えば、(Tree a, [Leaf, Branch])である。
Tree a はF-代数の圏の始対象であることにより、Tree aから各F-代数へ一意な準同型射を与える。この一意な準同型射はCatamorphismと呼ばれる。