Haskell入門ハンズオン! #3: 当日用資料 2/5

Haskell入門ハンズオン! #3: 当日用資料 2/5
====================================

はじめに
------

構文解析器をつくり、それを使って四則演算の式を読み込み、評価する。たとえば、つぎのような式を読み込む

    3+(5*4)

そして、この結果を計算して、つぎのように表示する。

    23

このように、文字列を決められたルールで解釈することを、構文解析とよぶ。今回は構文解析と、数値への評価を同時にやってしまう。

パーサコンビネータ
--------------

まず「パーサコンビネータ」を構成する関数群を定義する。「パーサコンビネータ」とは、構文解析器(パーサ)を組み上げるための道具だ。この道具を対話環境で試しながら作っていく。内容としては、拙書「Haskell - 教養としての関数型プログラミング」第20章の内容(P.298 - 310)を「ほぼ、まるまる」といった感じだ。

モジュールの導入
-------------

対話環境で使う関数をファイル内で導入しておく。こういうことは本番コードでは、あまりやらない。ここでは、ハンズオンでの便宜のため、このようなかたちとした。ファイルcalc.hsを、つぎのように作る。

    % vim calc.hs
    import Data.Maybe (listToMaybe, fromJust)
    import Data.Char (isDigit, isSpace, digitToInt)

予約語importを使って、モジュールを導入する。対話環境に読み込んでおこう。

```hs
*Main> :load calc.hs
```

パーサの型
--------

ここで、「パーサ」の型を考える。「文字列を読み込んで値をかえす関数」だと

```hs
String -> a
```

Haskellで標準的な文字列はString型の値だ。String型の値とは、実はChar型の値のリストだ。

```hs
*Main> ['x', 'y', 'z']
"xyz"
```

['x', 'y', 'z']と"xyz"とは、おなじものだ。また、「String -> a」の「a」は型変数だ。型変数は、実際に型が使われるときには、具体的な型(Char, Bool, Doubleなど)に置き換えられる。

ふたつのパーサをつなげることを考える。まえのパーサでパースしきれなかった文字列を、つぎのパーサにわたすことを考えると、パーサは結果の値だけでなく、「残りの文字列」もかえしたほうがいいだろう。すると、パーサの型は、つぎのようになる。

```hs
String -> (a, String)
```

(Foo, Bar)のような構造をタプルとよぶ。ふたつ以上の値をまとめるのに使うことができる。

さらに、パースの結果として、最終的には、ひとつにしぼるとしても、解析の途中では複数の候補が必要になることもある。パーサの型はさらに、つぎのようになる。

```hs
String -> [(a, String)]
```

[Foo]という表記は「Foo型の値のリスト」の型を意味する。この型全体の意味は、つぎのようになる。

    文字列を引数としてとり
    「パースの結果と残りの文字列」のリストをかえす関数

これから、パーサをあつかう関数をいくつか作る。そのたびに、String -> [(a, String)]を書くのは冗長だ。このようなとき、型に別名(型シノニム)をつけられる。ファイルcalc.hsに、つぎのように追加する。

```hs:calc.hs
type Parse a = String -> [(a, String)]
```

予約語typeを使って、型シノニムParseを定義した。型引数aのところには具体的な型がはいる。

    Parse Char ===> String -> [(Char, String)]
    Parse Bool ===> String -> [(Bool, String)]
    Parse Double ===> String -> [(Double, String)]

パーサコンビネータを構成する関数群
---------------------------

### いつも成功するパーサ

「いつも成功して、決められた値をかえすパーサ」を作る関数。

```hs:calc.hs
succeed :: a -> Parse a
succeed v inp = [(v, inp)]
```

いまは「何のためにあるか」は、わからなくていい。対話環境で試してみよう。

```hs
*Main> :reload
*Main> (succeed 123) "hello"
[(123,"hello")]
```

文字列を消費せずに123をかえすパーサに、文字列"hello"をあたえたら、ひとつの「結果の値123と残りの文字列"hello"」に解析された。

### 条件つきで1文字、読み込むパーサ

条件を満たす1文字を読み込むパーサを作る関数。

```hs:calc.hs
check :: (Char -> Bool) -> Parse Char
check p (c : cs) | p c = [(c, cs)]
check _ _ = []
```

関数checkの定義には、パターンマッチとガードという、ふたつの構文が使われている。第2引数のところの(c : cs)はパターンマッチだ。第2引数の文字列のうち、先頭の文字で変数cを束縛し、残りの文字列で変数csを束縛している。ちなみに、「値で変数を束縛する」は「値を変数に代入する」のように、頭のなかで変換するとわかりやすいかもしれない。

| p cのところがガードだ。これは、p cを評価した結果がTrueのとき、全体が=の左辺の[(c, cs)]に評価されるということだ。これらのパターンマッチとガードの、どちらかを満たさなければ、2行目にうつる。定義の2行目の_(アンダースコア)は、第1引数と第2引数とが、使われないということだ。引数は無視されて、全体は[](空リスト)に評価される。これは、1文字目cが条件を満たさなければ、パースは失敗するということだ。対話環境で試してみる。

```hs
*Main> :reload
*Main> check isDigit "123"
[('1',"23")]
*Main> check isDigit "abc"
[]
```

1文字目が数字なら成功し、そうでなければ失敗するパーサを作り、使った。

### 指定した1文字を読み込むパーサ

指定した1文字を読み込むパーサを作る関数。

```hs:calc.hs
char :: Char -> Parse Char
char c = check (== c)
```

(== c)は演算子の部分適用だ。演算子の第1引数のところが空いている。部分適用によって作られた関数に引数をあたえると、その「空いているところ」にはいる。たとえば(== c) 'a'のようにすると、'a' == cとしたのとおなじことになる。つまり、(== c)は引数と値cとを等値比較する関数になる。関数checkに「値cとの等値比較をする関数」をあたえると、指定した1文字cを読み込むパーサになる。対話環境で試してみる。

```hs
*Main> :reload
*Main> char 'a' "abc"
[('a',"bc")]
*Main> char 'a' "bcd"
[]
```

1文字目が指定した文字'a'であるとき、パースは成功し、文字'a'が消費され、文字'a'が結果になる。そうでなければ、パースは失敗する。

### ふたつのパーサのうち、どちらか

ふたつのパーサのうちのどちらかで解析するパーサを作る。パーサは「リストをかえす関数」なので、かえされたリストを結合すればいい。

```hs:calc.hs
alt :: Parse a -> Parse a -> Parse a
(p1 `alt` p2) inp = p1 inp ++ p2 inp
```

演算子(++)はリストを結合する。パーサの失敗を空リストとするので、パーサp1が失敗したとき、パーサp2の結果が全体の結果になる。逆も成り立つ。

まえに、演算子は()でかこむと、関数になると説明した。

```hs
*Main> 3 + 5
8
*Main> (+) 3 5
8
```

逆に、2引数関数は``(バッククォート)でかこむと、演算子になる。

```hs
*Main> mod 8 3
2
*Main> mod 8 `mod` 3
2
```

「``(バッククォート)で演算子になる」のは、関数を使うときだけでなく、関数を定義するときにも成り立つ。つまり、関数altの定義は、つぎとおなじことだ。

```hs
alt p1 p2 inp = p1 inp ++ p2 inp
```

「パーサp1とp2とを足し合わせる感じ」を表現したくて、定義にも演算子の構文を使った。対話環境で試してみよう。

```hs
*Main> :reload
*Main> (char 'a' `alt` check isDigit) "123"
[('1',"23")]
*Main> (char 'a' `alt` check isDigit) "abc"
[('a',"bc")]
```

「文字'a'、または、数字」の1文字をパースするパーサを作り、使った。

### パースの結果を加工する

パースした結果の値に関数を適用して、べつの値に変換する関数。

```hs:calc.hs
build :: Parse a -> (a -> b) -> Parse b
(p `build` f) inp = [ (f x, r) | (x, r) <- p inp ]
```

ここで使っているのは、リスト内包表記という構文糖だ。文字列inpに関数pを適用した結果としてリストができる。そのリストの要素すべてに対して、パターン(x, r)を使って、変数x, rを束縛し、式(f x, r)によって新しい値を作っている。対話環境で試してみよう。

```hs
*Main> :reload
*Main> (check isDigit `build` digitToInt) "123"
[(1,"23")]
```

関数digitToIntは数字の1文字を数値に変換する関数だ。check isDigitだけだと、結果は文字'1'になる。それに関数buildを使ってdigitToIntを適用することで、数値の1にしている。

### ふたつのパーサをつなげる

ふたつのパーサをつなげる演算子を定義する。

```hs:calc.hs
(>@>) :: Parse a -> Parse b -> Parse (a, b)
(p1 >@> p2) inp = [ ((x, y), r') | (x, r) <- p1 inp, (y, r') <- p2 r ]
```

ここでもリスト内包表記を使っている。パーサp1で解析した結果の残りの文字列rが、パーサp2の引数としてわたされている。パーサp1の複数の結果すべてに対して、パーサp2の複数の結果すべてが計算される。全体の結果として、それぞれのパースの結果の値x, yがタプルとして、まとめられて、それにさらに、パーサp2による解析の残りのr'を追加した。対話環境で試す。

```hs
*Main> :reload
*Main> (char 'a' >@> check isDigit) "a123"
[(('a','1'),"23")]
```

文字'a'をパースするパーサと、数字をパースするパーサとをつなげたパーサだ。

### つなげたパーサの、かたほうの結果だけを残す

ふたつのパーサをつなげるとき、どちらかのパース結果を捨てたいときがある。たとえば「123,456」のような文字列をパースするとき、,(カンマ)はパースの結果には必要ない。まえの結果と、うしろの結果について、それぞれを残す(他方を捨てる)ような、結合用の関数を定義する。

```hs:calc.hs
(>@) :: Parse a -> Parse b -> Parse a
p1 >@ p2 = (p1 >@> p2) `build` fst

(@>) :: Parse a -> Parse b -> Parse b
p1 @> p2 = (p1 >@> p2) `build` snd
```

関数fstとsndは、それぞれ、タプルの第1要素、第2要素を取り出す関数だ。これを関数buildによって、パースの結果に適用している。対話環境で試す。

```hs
*Main> :reload
*Main> (char 'a' >@ check isDigit) "a123"
[('a',"23")]
*Main> (char 'a' @> check isDigit) "a123"
[('1',"23")]
```

それぞれ、まえの値、うしろの値だけ結果として残る。

### 文字列のおわりを調べる

文字列のすべてを解析したことを確認するパーサを定義する。

```hs:calc.hs
eof :: Parse ()
eof "" = [((), "")]
eof _ = []
```

型()はユニット型と呼ばれる型であり、値()のみを値とする。情報量は0になる。簡単に言うと、パーサeofにはかえす結果がないということだ。対話環境で試す。

```hs
*Main> :reload
*Main> (char 'a' >@ eof) "a123"
[]
*Main> (char 'a' >@ eof) "a"
[('a',"")]
```

解析されていない文字列が残っていれば、パースは失敗する。

まとめ
-----

構文解析に使う基本的な道型を定義した。以下のパーサやパーサをあつかう関数だ。

    succeed, check, char, alt, build, (>@>), (>@), (@>)

これらを使って、パーサを組み立てていく。

[当日用資料 3/5へ](https://qiita.com/YoshikuniJujo/items/085fa142b0591cb4cb2b)