さかいです。

From: Nobuo Yamashita <nobsun / sampou.org>
Subject: [haskell-jp:9] Re: Generic Haskell: practice and theory
Date: Tue, 25 Feb 2003 19:51:47 +0900 (JST)

> > 型構築子の不動点を表す、
> >   newtype Fix f = In (f (Fix f))
> > くらいは私も見たことがあったのですが、
> 
> これって、実際にどのように使うのでしょう。型の意味は追えられている
> 気がしますが。。。

Fix f は X =~ f(X) を満たす型X(の中で最大の型)です。
(「=~」は同型関係)

データ型を通常の方法で定義するかわりにこのように定義する事で、
  out (In x) = x
  fold f   = f . fmap (fold f) . out
  unfold f = In . fmap (unfold f) . f
という風に、polytypicなfold/unfoldが定義出来るので、
catamorphism/anamorphismを用いたプログラミングに便利です。

例えば、これらを使うと、
リストとリストのlengthは以下のように定義されますが、

data ListF a x = Nil | Cons a x

instance Functor (ListF a) where
  fmap f Nil        = Nil
  fmap f (Cons a x) = Cons a (f x)

type List a = Fix (ListF a)

nil       = In Nil
cons x xs = In (Cons x xs)

length = fold f where
  f Nil = 0
  f (Cons _ n) = n + 1

--- length (cons 1 (cons 2 (cons 3 nil)))  => 3

同じようにして定義された他のデータ型(例えば以下の2分木)にも、
このfoldを同じように適用することが出来ます。

data TreeF a x = Leaf a | Branch x x

instance Functor (TreeF a) where
  fmap f (Leaf a)     = Leaf a
  fmap f (Branch x y) = Branch (f x) (f y)

type Tree a = Fix (TreeF a)

leaf a     = In (Leaf a)
branch x y = In (Branch x y)

fringe = fold f where
  f (Leaf a)     = [a]
  f (Branch x y) = x ++ y


> そういえば、型というより文脈のつくり方のような泥臭い手法ですけど。
> 私の場合こんなのでも、なるほどと関心したことがあります。
> 
>   data Hoge a を宣言するとき、a に特定具象型のみにしたいとき、
> 
>   data Nani a => Hoge a = Hoge a
> 
>   class Nani          -- method のないクラス
>   instance Nani OK    -- インスタンス宣言
>   
>   type KorehaOK = Hoge OK  
>   type KorehaNG = Hoge NG 
> 
>   これにより、Hoge OK は書けるけど Hoge NG を書けなくする手法です。
>   HTML や XML での要素の入れ子依存関係を制御する(特定の要素は、特定の
>   要素内でしか使えないようにする)手法として使われていました。

なるほど。これはクレバーな方法ですね。
今度から使ってみます。

--
酒井 政裕 / Masahiro Sakai
慶応義塾大学総合政策学部2年

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