top page > computer > haskell > web_lecture > for_programmer > poly_rec_type.html
更新日:
文責: 重城良国

再帰的な多相型

apple3.hs

はじめに

代数的データ型で樹構造を作る方法を学んだ。葉となる要素の型を型変数として一般化する。樹構造のコンテナとなる。

葉、花、実

型Appleの定義を枝のないものにもどす。

data Apple = Leaf | Flower | Fruit deriving Show

一般的な枝

枝の先にどの型の値をつけるかを指定できる一般的な枝を作る。

data Tree a = Branch (Tree a) (Tree a) | Atom a deriving Show

% ghci apple3.hs
*Main> Branch (Branch (Atom Leaf) (Atom Flower)) (Atom Fruit)
Branch (Branch (Atom Leaf) (Atom Flower)) (Atom Fruit)
*Main> :t Branch (Branch (Atom Leaf) (Atom Flower)) (Atom Fruit)
Branch (Branch (Atom Leaf) (Atom Flower)) (Atom Fruit)
:: Tree Apple

葉、花、実を枝につけるときには値構築子AtomでTree Apple型の値にしてやる必要がある。この枝にはどんな型の値でもつけられる。

*Main> Branch (Atom True) (Atom False)
Branch (Atom True) (Atom False)
*Main> :t Branch (Atom True) (Atom False)
Branch (Atom True) (Atom False) :: Tree Bool

値段を求める関数

前回と同じルールで値段を求める関数を作成する。まずは葉、花、実の単独での値段を求める関数だ。

priceA :: Apple -> Int
priceA Leaf = 50
priceA Flower = 80
priceA Fruit = 100

枝全体の値段を求める関数は

price1 :: Tree Apple -> Int
price1 (Atom a) = priceA a
price1 (Branch t1 t2) = 20 + price1 t1 + price1 t2

となる。

*Main> price1 $ Branch (Branch (Atom Leaf) (Atom Flower)) (Atom Fruit)
270

枝から外す

枝から外してフラットなリストにする関数はより一般的に書ける。

深さ優先探索

アトムであればその値ひとつのリストであり、枝であれば左右の木を平坦にしたリストを結合したものだ。

dfs :: Tree a -> [a]
dfs (Atom a) = [a]
dfs (Branch t1 t2) = dfs t1 ++ dfs t2

幅優先探索

[ここらへんをもっとちゃんと説明する]

bfs :: Tree a -> [a]
bfs = concat . bfsl . (: [])

bfsl :: [Tree a] -> [[a]]
bfsl = unfoldr $ \t -> if null t then Nothing else let
(ats, brs) = partitionEithers $ map branch t in
Just (ats, concat brs)

branch :: Tree a -> Either a [Tree a]
branch (Atom a) = Left a
branch (Branch t1 t2) = Right [t1, t2]

まとめ

再帰的なデータ型についてアトムとなる型を指定できるようにした。これは再帰的なコンテナということだ。このような型の値は要素を無限に収納可能なコンテナとなる。

課題

  1. 上記Treeに枝がひとつしかない値を追加した型を作成せよ
  2. 課題1で定義した樹の要素を深さ優先探索で列挙する関数を作成せよ

「再帰的な型」へもどる 「リスト」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics