nobsun です。

> 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を用いたプログラミングに便利です。

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

polytypic な fold/unfold よりも、抽象レベルの低いものですが、こんなのが
Tree についてはありますね。(gofer のサンプルコードにあったもの)
これは最初みたとき、「すげぇ」と思いました。

\begin{code}
class TreeCon t where
  branches :: t a -> [t a]

depth :: TreeCon t => t a -> Int
paths :: TreeCon t => t a -> [[t a]]
dfs :: TreeCon t => t a -> [t a]
bfs :: TreeCon t => t a -> [t a]

depth  = (1+) . foldl max 0 . map depth . branches

paths t | null br   = [[t]]
        | otherwise = [ t:p | b<-br, p<-paths b ]
          where br = branches t

dfs t = t : concat (map dfs (branches t))

bfs t = concat . lev
        where lev t = [t] : foldr cat [] (map lev (branches t))
	      cat   = longzw (++)
	      longzw f [] ys = ys
	      longzw f xs [] = xs
	      longzw f (x:xs) (y:ys) = f x y  : longzw f xs ys
\end{code}

こうしておくと、いろいろな木構造データについて、
深さ depth、深さ優先探索 dfs、幅優先探索 bfs、葉までのパス paths
が使えるというものです。たとえば、以下のようなもの

\begin{code}

data Tree a = Leaf a | Tree a :^: Tree a
instance TreeCon Tree where
  branches (Leaf n)  = []
  branches (l :^: r) = [l,r]

data LabTree l a  =  Tip a  |  LFork l (LabTree l a) (LabTree l a)
instance TreeCon (LabTree l) where
  branches (Tip x)       = []
  branches (LFork x l r) = [l,r]

data STree a = Empty | Split a (STree a) (STree a)
instance TreeCon STree where
  branches Empty         = []
  branches (Split x l r) = [l,r]

data GenTree a = Node a [GenTree a]
instance TreeCon GenTree where
  branches (Node x gts) = gts

\end{code}

--nobsun

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/