Catamorphism

圏論において、Catamorphism(ギリシャ語: κατά = 下方へ または ～に従って; μορφή = 形式または形)は、始代数から他の代数への唯一の準同型射を意味する。この概念は関数型プログラミングへfoldとして応用されている。

Anamorphismはこの双対となる概念である。Hylomorphismも参照。

関数型プログラミングにおける Catamorphism

Catamorphismは関数型プログラミングにおいてリストの fold と呼ばれる操作を、始代数として表現できる任意の代数的データ型に一般化したものである。

プログラミングにおいて Catamorphism の概念を導入した最初の出版物の一つは、“Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire”, by Erik Meijer et al.[1]で、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, (+))

ここで、foldTree (f, g) はデータ型Tree a の catamorphism で、 treeDepth とsumTree は代数と呼ばれる。

圏論における Catamorphism

圏論は、全ての始データ型を記述する一般的な定義を与えるために必要な概念を提供する(関数型プログラミングにおける関数を集合の圏や関連した具体的な圏の射と同一視することによって)。これはGrant Malcolmによって行われた。^[1]^[2].

上記の例に戻り、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と呼ばれる。

一般の場合

圏論では、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に対して、以下の関係式によって定義することもできる。

$h=\mathrm {cata} \ f$
$h\circ in=f\circ Fh$

記法

cata f は別の記法 $(\!|f|\!)$ と記されることがある。使用されている開いた括弧は「バナナ括弧」として知られ、Meijer 1991などで記載された後は、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): pp. 255–279, doi:10.1016/0167-6423(90)90023-7 .

参考文献

Erik Meijer (computer scientist), Maarten Fokkinga, and Ross Paterson. "Functional Programming with Bananas, Lenses, Envelopes, and Barbed Wire".
Ki Yung Ahn and Tim Sheard (2011). "A hierarchy of mendler style recursion combinators: taming inductive datatypes with negative occurrences". Proceedings of the 16th ACM SIGPLAN international conference on Functional programming (ICFP '11).

外部リンク

Catamorphisms page on Haskellwiki
Catamorphisms by Edward Kmett at Google Knol
Catamorphisms in F# (Part 1, 2, 3, 4, 5, 6, 7) by Brian McNamara
Catamorphisms in Haskell

[1] Malcolm, Grant (1990) (Ph.D. Thesis), Algebraic types and program transformation, University of Groningen .

[2] Malcolm, Grant (1990), “Data structures and program transformation”, Science of Computer Programming 14 (2-3): pp. 255–279, doi:10.1016/0167-6423(90)90023-7 .

[1]

[2]