Catamorphism
圏論において、Catamorphism(ギリシャ語: κατά = 下方へ または ～に従って; μορφή = 形式 または 形)は、始代数から他の代数への唯一の準同型射を意味する。この概念は関数型プログラミングへfoldとして応用されている。
Anamorphismはこの双対となる概念である。Hylomorphismも参照。
関数型プログラミングにおけるCatamorphism
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を適用するものである。
例
次の例はHaskellによるもの。
data Tree a = Leaf a
            | Branch (Tree a) (Tree a)type TreeAlgebra a r = (a -> r, r -> r -> r)foldTree :: TreeAlgebra a r -> Tree a -> rfoldTree (f, g) (Leaf x)     = f xfoldTree (f, g) (Branch l r) = g (foldTree (f, g) l) (foldTree (f, g) r)treeDepth :: TreeAlgebra a IntegertreeDepth = (const 1, \l r -> 1 + max l r)sumTree :: (Num a) => TreeAlgebra a asumTree = (id, (+))

ここで、foldTree (f, g) はデータ型Tree a のcatamorphismで、 treeDepth とsumTree は代数と呼ばれる。
記法
cata f は別の記法  と記されることがある。使用されている開いた括弧は「バナナ括弧」として知られ、Meijer 1991などで記載された後は、Catamorphismは時に「バナナ」と呼ばれる。