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

再帰的な型

はじめに

関数定義と同じように型も再帰的に定義できる。

りんご屋さん

apple1.hs

問題定義

すこし変わったりんご屋さんがある。りんごの実だけではなく葉や花も「りんご」として売っている。

のように陳列されている。このお店で買い物をして合計金額を求めてみよう。

葉、花、実を含むりんご型を定義する。

data Apple = Leaf | Flower | Fruit deriving Show

買い物かごも用意しよう。

type Basket = [Apple]

値段の対応

値段の対応を表現する関数を定義する。

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

買い物かごの合計金額

price :: Basket -> Int
price = sum . map price1

% ghci apple.hs
*Main> price [Leaf, Leaf, Flower, Fruit, Fruit, Fruit]
480

りんごの枝

apple2.hs

商売の拡張

商品の種類を増やす。りんごの枝を追加する。りんごの枝はふたつにわかれその先にりんごの葉、花、実がつく。枝の先につくのはそれだけではない。枝自体もだ。りんごの枝は次々と枝分かれする。値段は枝分かれごとに20円足す。葉、花、実の値段は変わらない。

新しい商品をモデル化する型を作る。

data Apple = Leaf | Flower | Fruit | Branch Apple Apple
deriving Show

型Appleの定義に型Appleが使われている。再帰的な定義となっている。値の例を示す。

Branch Leaf Flower

Branch Fruit (Branch Fruit Leaf)

値段の計算

葉、花、実の値段は同じだ。

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

枝は再帰的に計算する。

price1 (Branch a1 a2) = 20 + price1 a1 + price1 a2

*Main> :load apple2.hs
*Main> price1 $ Branch (Branch Fruit Leaf) Flower
270

枝から取る

葉、花、実を枝から外して並べる。ひとつの枝を先のほうまでたどっていく方法と、根本に近いものから外していく方法とがある。前者が深さ優先探索で後者が幅優先探索だ。

深さ優先探索

枝の全てのアイテムは、左の枝の全てのアイテムと右の枝の全てのアイテムとを足したものだ。

dfs :: Apple -> [Apple]
dfs (Branch a1 a2) = dfs a1 ++ dfs a2
dfs a = [a]

*Main> :reload
*Main> dfs $ Branch (Branch Fruit Leaf) Flower
[Fruit,Leaf,Flower]

幅優先探索

関数bfslはApple型のリストを次々にわたしながらApple型のリストを集めてリストを作る。関数bfslの引き数と返り値とを変換することで関数bfsを作る。

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

(: [])によって引数をApple型からApple型のリストに変換している。(: [])は空リストの前に要素を追加することで単一の要素から成るリストを作る。bfslの返り値は枝の各レベルごとに分かれたリストのリストになっている。関数concatでこれを平坦なリストにする。

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

branch :: Apple -> Either Apple [Apple]
branch (Branch a1 a2) = Right [a1, a2]
branch a = Left a

まずnull asによって空リストかどうかをチェックしている。空リストであればNothingとする。これは関数unfoldrにリストの列挙の終了を教える。関数branchは枝でなければLeft値としてアトムであるApple値を返し、枝であればその左右の値をリストにしてRight値として返す。partitionEithersによってアトム(Left値)のリストと枝(Right値)のリストに分ける。アトムのリストは結果のリストの1要素となる。枝のリストは平坦化され状態として次の操作に渡される。

*Main> :reload
*Main> bfs $ Branch (Branch Fruit Leaf) Flower
[Flower,Fruit,Leaf]

[このあたり説明をわかりやすくする必要あり、でなければ消すか]

まとめ

型は再帰的に定義できる。

課題

  1. マトリョーシカを表現する型を作成せよ
  2. マトリョーシカ人形の数を数える関数を作成せよ
  3. 数を指定してマトリョーシカ人形を作成する関数を定義せよ

「Either型」へもどる 「再帰的な多相型」へ

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