nobsun です。

> 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 で置き換えたものです)

あっ。なるほど、
"Why Functional Programming Matters" の§3 の説明を思い出しました。
List の場合にははまさしく、foldr で表現されるものという訳ですね。

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

-- ふと思ったのですが、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を使って定義できます。

unfold は destructor を使って、型構築子を定義する関数というわけですね。

> ちなみに、もっと専門的な言い方をすれば、
> catamorphism = initial algebra からのユニークな homomorphism
> anamorphism  = final coalgebra へのユニークな homomorphism

あぅぅ。トラウマがぁ。。。失礼しました。f(^^;)

> で、polytypicなfold/unfoldはこの事実を利用して定義されています。

なるほど、なるほど。φ(..)_ 
よく分りました。いやぁ。こういう高度な抽象化の話しは、分ると面白いですねぇ。
分りやすい説明ありがとうございます。

Haskell の抽象化能力は本当にすごいとあらため感じます。

--
Nobuo Yamashita                 mailto:nobsun / sampou.org
  I love programming.           http://www.sampou.org/
  I love pencil puzzles.        http://www.puzzle.jp/


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