Catamorphism

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

圏論において、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の一般化である。

[編集]

次の例は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 acatamorphismで、 treeDepthsumTree代数と呼ばれる。

圏論におけるCatamorphisms[編集]

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

上記の例に戻り、ra + r × rを対応させる関手Fを考える。 この特定の場合に対応するF代数は組(r, [f1,f2])である、ここでr は対象であり、二つの射 f1f2

f1: a → r
f2: r × r → r

として定義される。

この関手FにおけるF-代数の圏の場合、始代数は存在すれば、Treeを表現する。これはHaskellの用語で言えば、(Tree a, [Leaf, Branch])である。

Tree aF-代数の圏の始対象であることにより、Tree aから各F-代数へ一意な準同型射を与える。この一意な準同型射はCatamorphismと呼ばれる。

一般の場合[編集]

圏論では、CatamorphismとAnamorphism圏論的双対である。

これは以下を意味する。(A, in)をある圏からそれ自身への自己関手Fに対する始代数とする。 従って、inFAからAへの射であり、これが始であると仮定したので、つまり、(X, f)を他のF-代数(射f : FXXのこと)とすると、(A, in)から(X, f)への一意な準同型射hが常に存在すると仮定したので、AからXへの射hで、h . in = f . Fhを満たすものもまた一意に存在する。 そして、各fに対して一意に指定された射hcata fで表す。

言い換えれば、固定されたFAinに対して、以下の関係式によって定義することもできる。

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

記法[編集]

cata f は別の記法 (\!|f|\!) と記されることがある。使用されている開いた括弧は「バナナ括弧」として知られ、Meijer 1991などで記載された後は、Catamorphismは時に「バナナ」と呼ばれる。

関連項目[編集]

参考リンク[編集]

  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 .

参考文献[編集]

外部リンク[編集]