さかいです。

From: Nobuo Yamashita <nobsun / sampou.org>
Subject: [haskell-jp:21] Re: Generic Haskell: practice and theory
Date: Wed, 26 Feb 2003 10:32:10 +0900 (JST)

> nobsun です。

> catamorphism/anamorphism は言葉としては聞いたことがあるのですが。。。
> Haskell のプログラムとしては、どのようなもの(変換?性質?)を指すのでしょうか?

うまく説明できるかどうかあまり自信がないですが、
とりあえず説明してみます。

---

Fixを使ったpolytypicな定義は多少トリッキーなので
通常の方法で定義されたリスト
data List a = Nil | Cons a (List a)
を例にcatamorphismについて説明します。

まず、このデータ型 List a は
Nil  :: List a
Cons :: a -> List a -> List a
という二つのデータ構築子を持ち、値としては例えば
Cons 3 (Cons 2 (Cons 1 Nil))
のようなものがあります。

catamorphismはこのような値を受け取って
含まれるデータ構築子を別の値/関数
z :: X
f :: a -> X -> X
で置き換えた f 3 (f 2 (f 1 z)) のような値を返す関数の事です。
(このz,fの型はデータ構築子の型に含まれる List a を X で置き換えたものです)

このようなデータ構築子の置換によって非常に多くの関数が定義できます。
例えば、
z = 0
f a n = n + 1
とすると、先のメールでも取り上げたlength関数になります。

具体的に定義すると、
length Nil = z  where z = 0
length (Cons x xs) = f x (length xs)  where f a n = n + 1
ですが、ここからfとzをパラメタライズすると、再帰演算子
fold :: x -> (a -> x -> x) -> (List a -> x)
fold z f Nil         = z
fold z f (Cons x xs) = f x (fold z f xs)
となり、このfoldを使って List a の全てのcatamorphismを定義できます。

---

逆にanamoprhismはデータ型の破壊子(destructor)の振舞を与えることで
定義される関数です。
(……と言ってしまうのもまずい気がしますが、良い説明が思い付きません)

data Stream a = Stream {shead :: a, stail :: Stream a}
というデータ型を考えると
shead :: Stream a -> a
stail :: Stream a -> Stream a
というdestructorを持っていて、
値の振舞はこれらのdestructorの振舞のみによって規定されています。
すなわち、destructorの振舞を与えることで値を定義出来ます。

で、anamorphismではどのような形でこの振舞を与えるかというと、
destructorの型に含まれるStream aを型Xで置き換えた
h :: X -> a
t :: X -> X
のような関数を用いて与えます。 

具体的には
incseq :: Integer -> Stream Integer
incseq x = Stream (h x) (incseq (t x)) where
  h n = n
  t n = n + 1
のような関数が Stream Integer のanamorphismの例です。

ここからhとtをパラメタライズすることで、再帰演算子
unfold :: (x -> a) -> (x -> x) -> (x -> Stream a)
unfold h t x = Stream (h x) (unfold h t (t x))
が得られ、Stream a の全てのanamorphismはこのunfoldを使って定義できます。

---

ちなみに、もっと専門的な言い方をすれば、
catamorphism = initial algebra からのユニークな homomorphism
anamorphism  = final coalgebra へのユニークな homomorphism
で、polytypicなfold/unfoldはこの事実を利用して定義されています。

--
酒井 政裕 / Masahiro Sakai

--
ML: haskell-jp / quickml.com
使い方: http://QuickML.com/