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 -> r
foldTree (f, g) (Leaf x) = f x
foldTree (f, g) (Branch l r) = g (foldTree (f, g) l) (foldTree (f, g) r)
treeDepth :: TreeAlgebra a Integer
treeDepth = (const 1, \l r -> 1 + max l r)
sumTree :: (Num a) => TreeAlgebra a a
sumTree = (id, (+))
ここで、codice_1 はデータ型codice_2 の catamorphism で、 codice_3 とcodice_4 は代数と呼ばれる。
圏論における Catamorphism.
圏論は、全ての始データ型を記述する一般的な定義を与えるために必要な概念を提供する(関数型プログラミングにおける関数を集合の圏や関連した具体的な圏の射と同一視することによって)。これはGrant Malcolmによって行われた。.
上記の例に戻り、codice_5にcodice_6を対応させる関手"F"を考える。
この特定の場合に対応するF代数は組(codice_5, [codice_8,codice_9])である、ここでcodice_5 は対象であり、二つの射 codice_8 と codice_9 は
として定義される。
この関手"F"における"F"-代数の圏の場合、始代数は存在すれば、codice_15を表現する。これはHaskellの用語で言えば、codice_16である。
codice_17 は"F"-代数の圏の始対象であることにより、codice_17から各"F"-代数へ一意な準同型射を与える。この一意な準同型射は"Catamorphism"と呼ばれる。
一般の場合.
圏論では、CatamorphismとAnamorphismは圏論的双対である。
これは以下を意味する。("A", "in")をある圏からそれ自身への自己関手"F"に対する始代数とする。
従って、"in"は"FA"から"A"への射であり、これが始であると仮定したので、つまり、("X", "f")を他のF-代数(射"f" : "FX" → "X"のこと)とすると、("A", "in")から("X", "f")への一意な準同型射"h"が常に存在すると仮定したので、"A"から"X"への射"h"で、"h . in = f . Fh"を満たすものもまた一意に存在する。
そして、各"f"に対して一意に指定された射"h"をcata fで表す。
言い換えれば、固定された"F"、"A"、"in"に対して、以下の関係式によって定義することもできる。
記法.
cata "f" は別の記法 formula_3 と記されることがある。使用されている開いた括弧は「バナナ括弧」として知られ、などで記載された後は、Catamorphismは時に「バナナ」と呼ばれる。