「Catamorphism」の版間の差分

削除された内容追加された内容

インライン

2018年1月21日 (日) 06:22時点における版

圏論において、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): 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): 255–279, doi:10.1016/0167-6423(90)90023-7 .

[1]

[2]

@@ 35行目: / 35行目: @@
 ここで、<code>foldTree (''f'', ''g'')</code> は[[抽象データ型|データ型]]<code>Tree ''a''</code> の''catamorphism''で、 <code>treeDepth</code> と<code>sumTree</code> は''代数''と呼ばれる。
-== [[圏論]]におけるCatamorphisms ==
+== [[圏論]]におけるCatamorphism ==
 [[圏論]]は、全ての始データ型を記述する一般的な定義を与えるために必要な概念を提供する(関数型プログラミングにおける関数を[[圏|集合の圏]]や関連した具体的な圏の[[射_(圏論)|射]]と同一視することによって)。これはGrant Malcolmによって行われた。<ref>{{Citation |last=Malcolm |first=Grant |year=1990 |title=Algebraic types and program transformation |format=Ph.D. Thesis |publisher=University of Groningen}}.</ref><ref>{{Citation |last=Malcolm |first=Grant |year=1990 |title=Data structures and program transformation |periodical=Science of Computer Programming |volume=14 |issue=2-3 |pages=255–279 |doi=10.1016/0167-6423(90)90023-7}}.</ref>.