プログラミング Haskell 付録 C 訳者による関数の解説
最後に付録 C を読みます。本文中に出てきた関数定義についての補足があります。
- string は do 文のなかで再帰しているということなので特になし
- many と many1 - パーサーのとこで出てきたこの2つの関数は読み解くのが難しかったです
パーサー p を 0回くりかえす関数 m0 は
m0 p = return []
パーサー p を 0回または 1回くりかえす関数 m1 は
m1 p = do v1 <- p return [v1] +++ return []
↑わざと冗長に書いてます
パーサー p を 0、1、2回のいずれか繰り返す関数 m2 は
m2 p = do v1 <- p v2 <- p return [v1, v2] +++ do v1 <- p return [v1] +++ return []
v1 <- p の部分をくくり出して
m2 p = do v1 <- p vs <- do v2 <- p return [v2] +++ return [] return (v1:vs) +++ return []
中央の部分は m1 に置換できるので
m2 p = do v1 <- p vs <- m1 return (v1:vs) +++ return []
よって many は以下のように自己再帰的に定義できる
many p = do v <- p vs <- many p return (v:vs) +++ return []
さらに many1 は many を使って以下のように定義できる
many1 = do v <- p vs <- many p return (v:vs)
そうすると今度は many の中に many1 の定義があることがわかるので以下のように書き換えられる。
many = many1 p +++ return []
こうして変遷をみると納得ですね。
- subs - リストの部分リスト全てのリストを返す関数。これも定義はシンプルですが難しい
まず実際に小さめのリストで結果を書き出してみます。「例示は理解の試金石」*1ですね。
subs [] = [[]] subs [3] = [[], [3]] subs [2,3] = [[], [3], [2], [2,3]] subs [1,2,3] = [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]
こうしてみるとリストの「前に」要素を追加していくと追加する前の結果が前半に共通して現われることがわかります。そこで以下のような形で定義が書けるとわかります。
subs (x:xs) = yss ++ (ここは後半) where yss = subs xs -- むだに where 節使っていますが次の布石です
さらに後半をよくみると、前半のリストのにそれぞれ新しい要素を cons したものになっているのでこう書けます。
subs (x:xs) = yss + map (x:) yss where yss = subs xs
これはすごい。
interleave と perms の解説もありましたが subs とほぼ同じ手法なので省略します。リスト操作関数の定義の作り方は数学の証明みたいですね。
これで長かった「プログラミング Haskell」も読了です。写経したり練習問題を実際に解きながら進めたので時間がかかりましたが、おかげで Haskell にかなり親しめたと思います。
次はやっぱり「プログラミングコンテストチャレンジブック」にしようと思います。
