練習問題を解いてみる

Haskellに関してちょっとづつ調べてみてるけど，難しいって思う以外，全然進みません．そこで，情報処理学会に連載されてるhttp://www.ipsj.or.jp/07editj/promenade/という記事の例題を解いてみようと思いました．今回トライしてみたのは，2005年5月号の「木(tree)で遊ぶ」http://www.ipsj.or.jp/07editj/promenade/4605.pdfの例題1についていた，練習問題1です．

例題1の問題は，「末端のノードがn個の二分木を列挙せよ」というもので，

練習問題1 trees 4 の評価結果が

[(L^(L^(L^R))),(L^((L^R)^R)),((L^R)^(L^R)),((L^(L^R))^R),(((L^R)^R)^R)]

と表示されるようDumbTree用のshowの定義を変更せよ．

というのが練習問題でした．私の答えはこんな感じ．

instance Show DumbTree where
  show (Fork Empty Empty) = "(" ++ "L"    ++ "^" ++ "R" ++ ")"
  show (Fork l Empty)     = "(" ++ show l ++ "^" ++ "R" ++ ")"
  show (Fork Empty r)     = "(" ++ "L"    ++ "^" ++ show r ++ ")"
  show (Fork l r)         = "(" ++ show l ++ "^" ++ show r ++ ")"

元々，DubmTreeという型は次のように定義されていました．

data DumbTree = Empty | Fork DumbTree DumbTree

これは『DumbTree型は，末端ノードEmptyかあるいは再帰的に二つの部分木DumbTreeを含むForkノードで構成』と読むらしいです．最初は，Fork/Emptyというのが何者か（記事にはデータ構成子と書いてある）がわからず，ずっと悩んでいました．組み込み型なのかと思ってぐぐったけど，全然ヒットなし．データ構成子でぐぐると，変わった名前が出てきたりして，予め組み込まれた名前とも思えません．ふと思いついて，プログラム中のキーワードを":%s/Fork/Mata/g", ":%s/Empty/Kara/g" （vimでの置換表現）とやっても動いたので，ユーザ定義名なんだということに気がついたのでした．そうしてこうして，最終的にできたプログラムは以下のようになります．

-- data宣言: 組込型以外の型を定義
-- 『DumbTree型は，末端ノードEmptyかあるいは
-- 再帰的に二つの部分木DumbTreeを含むForkノードで構成』と，読む
--   DumbTree : 型構成子
--   Empty, Fork : データ構成子
data DumbTree = Empty | Fork DumbTree DumbTree

-- DumbTreeがShowクラスのインスタンスだと宣言
-- show関数は，ある型のデータを表示するための関数
instance Show DumbTree where
  show (Fork Empty Empty) = "(" ++ "L"    ++ "^" ++ "R" ++ ")"
  show (Fork l Empty)     = "(" ++ show l ++ "^" ++ "R" ++ ")"
  show (Fork Empty r)     = "(" ++ "L"    ++ "^" ++ show r ++ ")"
  show (Fork l r)         = "(" ++ show l ++ "^" ++ show r ++ ")"

-- trees: 『Int型からDumbTree型を要素とするリストへの関数』という型
-- 整数からDumbTreeのリストへ
trees :: Int -> [DumbTree]
trees 1 = [Empty]
-- "splits1 n"で構成されるリストの各要素である二つ組み(xs, ys)に
-- 関数lrsを適用してできたリストの要素である二つ組み(ls, rs)に
-- 関数joinsを適用してできたリスト（複数）に
-- 関数concatを適用して一つのリストにする
trees n = concat [joins ls rs | (ls, rs) <- [lrs xs ys | (xs, ys) <- splits1 n]]

-- splits1: 『Int型からInt型の二つ組みのリストへの関数』という型
-- 整数から，和がその数になる整数の二つ組みのリストへ
splits1 :: Int -> [(Int, Int)]
splits1 1 = []
splits1 n = (1, n-1) : [(i+1, j) | (i, j) <- splits1 (n-1)]

-- lrs: 『ふたつのInt型から，DumbTreeリストの二つ組みへの関数』という型
-- 二つの整数から，それぞれの大きさのDumbTreeのリストの二つ組みへ
lrs :: Int -> Int -> ([DumbTree], [DumbTree])
lrs xs ys = (trees xs, trees ys)

-- joins: 『ふたつのDumbTreeリスト型からDumbTreeリスト型への関数』という型
-- ふたつのDumbTreeリストからそれぞれを左右に持つDumbTreeのリスト
joins :: [DumbTree] -> [DumbTree] -> [DumbTree]
joins ls rs = [Fork l r | l <-ls, r <- rs]

先はとっても長いです．まず，時間を作らないと… orz