これまでリストを再帰的に扱う方法を学んできた。特殊なリストとして、String がある。String とは Char のリストであり、以下のように定義されている。(type は、型の別名を定義する構文。)
type String = [Char]今回は、文字列の構文を解析する。コンピュータで使われているデータ構造には、再帰的に定義されたものが多い。分かりやすい例としては、木構造がある。また、再帰的に定義された構造が、文字列として表現されていることも多い。プログラミング言語のコードが最たる例である。
再帰構造が文字列として表現されている別の例としては、電子メールが挙げられる。電子メールは、以下のような相互再帰的な構造を持つ。
- メールは、ヘッダとシングルパートからなる
- シングルパートは、テキストかマルチパートかメールである
- マルチパートは、0個以上のシングルパートからなる
このような構造をループのみで解析するのは不可能ではないが、かなり難しいしバグも入り込みやすい。再帰的に定義されている構造は、やはり再帰を用いて解析するのが簡潔で明瞭である。
入力として与えられた文字列の中から、開き括弧と閉じ括弧の組の数を数えたい。問題を簡単にするため、入力の文字列は開き括弧と閉じ括弧のみを含むとする。たとえば、"()(())" の中には3つの括弧がある。これを実現するためには、横方向に再帰(繰り返し)することと、入れ子構造に対して再帰することが必要になる。
いきなり最終的な関数を書くのは難しいので、以下のようなステップを踏むことにする。
- 括弧の組を横方向に数える関数を書く
- 入れ子の括弧を数える関数を書く
- これら2つの関数をマージして最終的な関数を書く
括弧の組を横方向に数える関数 my_paren_seq を定義したい。この関数の利用例はこうだ。
> my_paren_seq ""
0
> my_paren_seq "()"
1
> my_paren_seq "()()"
2
関数型言語で初等的なパーサを書くときには、次のような型を持つ関数を書くのが常套手段である。すなわち、入力として文字列を取る。出力として、「解析結果」と「消費しなかった文字列」の組を返す。
この常套手段を踏まえて、まず「閉じ括弧」を解析する関数を書こう。この関数は、入力の先頭が閉じ括弧であれば、解析結果として 1 を返す。そうでなければ、安直にエラーとする。(まじめにやるなら Maybe を使おう。)
my_close :: String -> (Int, String)
my_close (')':left) = (1,left)
my_close _ = error "no my_close parenthesis"これまで整数の型としては、大きさに制限のない Integer を用いてきたが、今回は大きさに制限のある Int を使う。通常のプログラミングでは、効率を考えて、Integer よりも Int を使う方が多い。
次に my_paren_seq を以下のように定義する。my_paren_seq は、入力の先頭が開き括弧であれば、入力の残りを引数として my_open_seq を呼び出す。そうでければ、0 と入力文字列を返す。
my_paren_seq :: String -> (Int, String)
my_paren_seq ('(':left0) = my_open_seq left0
my_paren_seq left0 = (0,left0)まだ、my_open_seq は定義してないが、そこは通らない利用例を以下に示す。
> my_paren_seq ""
(0,"")
> my_paren_seq "foo"
(0,"foo")
空文字列に対して、0 を返すとともに再帰が止まる。入力として括弧以外はないことを想定しているが、括弧以外の文字列が来た場合は、そのまま返す(なるべくエラーにしないようにしている)。
次に、my_open_seq を定義しよう。開き括弧の直後は、閉じ括弧であるから my_close を呼ぶ。そして入力の残りに対して、自分自身を呼び出して、横方向の繰り返しを実現すればよい。
my_open_seq :: String -> (Int, String)
my_open_seq left0 = (cnt1+cnt2, left2)
where
(cnt1,left1) = my_close left0
(cnt2,left2) = my_paren_seq left1これで完成だ。一つの関数で実現することもできるが、三つの関数として定義することで、以下で定義する関数と比較しやすくしてある。
入れ子の括弧を数える関数 my_paren_rec を実装しよう。使用例は、以下の通り。
> my_paren_rec ""
0
> my_paren_rec "()"
1
> my_paren_rec "(())"
2
my_paren_rec の骨格は、my_paren_seq と同じである。
my_paren_rec :: String -> (Int, String)
my_paren_rec ('(':left0) = my_open_rec left0
my_paren_rec left0 = (0,left0)次に my_open_rec の実装を考える。開き括弧の直後には、また開き括弧が来るかもしれない。さらに対応する閉じ括弧も処理する必要がある。よって、my_open_seq の場合とは、逆の順番の処理をすることになる。
my_open_rec :: String -> (Int, String)
my_open_rec left0 = (cnt1+cnt2, left2)
where
(cnt1,left1) = my_paren_rec left0
(cnt2,left2) = my_close left1my_paren_seq と my_paren_rec をマージして、最終的な関数 my_paren を実現しよう。使用例を以下に示す。
> my_paren "(())()"
3
> my_paren "(()())"
3
> my_paren "((())())(())"
6
関数 my_paren の骨格はこれまでと変わらない。
my_paren :: String -> (Int, String)
my_paren ('(':left0) = my_open left0
my_paren left0 = (0,left0)my_open_seq と my_open_rec を参考にしながら、my_open を実装しなさい。
my_open :: String -> (Int, String)
my_open left0 = undefined次の例として、数式を取り挙げよう。まず、簡単な数式を計算する関数を実装し、次により一般的な数式を計算する関数を実現する。
###簡単な数式を計算する
一桁の数値と足し算からのみなる数式を計算する関数 my_expr_simple を実装しよう。利用例は、以下の通り。
> my_expr_simple "1"
(1,"")
> my_expr_simple "1+2"
(3,"")
データ構造の構文は、BNF (Backus-Naur form)で与えられることが多い。この簡単な数式の BNF を以下に示す。
<expr_simple> ::= <nat> (’+’ <expr_simple> | ε)
<nat> ::= ’0’ | ’1’ | ’2’ | ...
BNF のメタ記号を簡単に説明する。
<foo>は非終端記号である。'a'は終端記号である。この場合、a という文字を表す。|は「または」を表す。(と)で囲まれた部分は優先順位が高い。- ε は、何もないことを表す。
よって、<nat> は一桁の数字を表現し、<expr_simple> は一桁の数字の足し算を表す。(この BNF の定義では、足し算が右結合となっている。本来の左結合すると、問題が複雑になるので、敢えて右結合にしてある。)
まず、<nat> に対応する関数 my_nat を実装しよう。(Data.Char を import する必要がある。)
my_nat :: String -> (Int, String)
my_nat (x:xs)
| isDigit x = (c2i x, xs)
my_nat _ = error "my_nat"
c2i :: Char -> Int
c2i x = ord x - ord '0'実際に使ってみる。
> my_nat "1"
(1,"")
> my_nat "2a"
(2,"a")
次に my_expr_simple を定義する。横方向に再帰するだけなので、それほど難しくはない。以下の定義を BNF の <expr_simple> と照らし合わせて理解して欲しい。
my_first :: (a -> c) -> (a,b) -> (c,b)
my_first f (x,y) = (f x, y)
my_expr_simple :: String -> (Int, String)
my_expr_simple xs = case my_nat xs of
(x, '+':left) -> my_first (x+) (my_expr_simple left)
xl -> xlコードを簡潔にするために補助関数 my_first が定義してある。my_first は、第一引数に取った関数を、第二引数に取った組の「左側の要素」に適応する。このドリルで、はじめて case of というパターンマッチのための構文が出てきたことに注意。
(xl -> xl の部分は、(x,left) -> (x,left) と書く方が分かりやすいかもしれないが、冗長である。)
###より一般的な数式を計算する
次に掛け算と括弧を許すより一般的な数式を考えよう。この数式を計算する関数を my_expr とすると、利用例は以下のようになる。
> my_expr "(1+2)*3"
(9,"")
> my_expr "(1+2)*(3+4)+5"
(26,"")
この数式のBNFを以下に示す。
<expr> ::= <term> (’+’ <expr> | ε)
<term> ::= <factor> (’*’ <term> | ε)
<factor> ::= ’(’ <expr> ’)’ | <nat>
<nat> ::=’0’ | ’1’ | ’2’ | ...
<expr> の定義には <expr> が使われているので再帰的である。また、
<expr>は<term><term>は<factor><factor>は<expr>
を使って定義してあるので、相互再帰となっている。
<expr> と <term> が分かれていることで、足し算よりも掛け算の方が優先順位が高いことが表現されている。
####演習
この数式を計算する関数を実装しなさい。my_nat は、上記のコードをそのまま使うこと。
my_expr :: String -> (Int, String)
my_expr xs = undefined
my_term :: String -> (Int, String)
my_term xs = undefined
my_factor :: String -> (Int, String)
my_factor xs = undefined今回は文字列の構造を解析するために、素朴な方法でパーサを定義した。通常、このような問題を解くときは、洗練されたパーサ・コンビネータ・ライブラリを使う。その一つである有名な Parsec を使って、今回の問題を解いコードも用意した。参考までに眺めてみるとよい。モナドという技術をのおかげで、入力文字列やエラー処理が裏に隠れるため、読みやすく保守しやすいコードとなる。