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

はじめに

パーサを組み立てるための基本的な関数を定義した。それらを使って、空白で区切った数値をパースする。まずは、パーサをリストのパーサに変換する関数を定義する。

リストのパーサ

「ひとつの要素を解析するパーサ」を、「複数の要素を解析して、リストとしてかえすパーサ」に変換する。ポイントは、「0要素以上のリストを解析するパーサ」と、「1要素以上のリストを解析するパーサ」とを同時に作ること、だ。関数listとlist1とを定義する。ファイルcalc.hsに関数listとlist1とを追加する。

calc.hs

list, list1 :: Parse a -> Parse [a]
list p = succeed [] `alt` list1 p
list1 p = (p >@> list p) `build` uncurry (:)

uncurry (:)のところは、つぎの例をみてみよう。

*Main> uncurry (:) ('h', "ello")
"hello"

(先頭の値、残りのリスト)のようなタプルを、もとのリストに変換している。このbuild以下の部分は「かたちを整えている」だけだ。その部分には、いちど目をつぶろう。

list p = succeed [] `alt` list1 p
list1 p = p >@> list p

0要素以上のリストは「0要素のリスト、または、1要素以上のりすと」である。そして、1要素以上のリストは「ひとつの要素に、0要素以上のリストを続けたもの」だ。対話環境で試してみる。

*Main> :reload
*Main> list (check isDigit) "123"
[("","123"),("1","23"),("12","3"),("123","")]
*Main> list1 (check isDigit) "123"
[("1","23"),("12","3"),("123","")]

関数listで0要素以上のくりかえしが、関数list1で1要素以上のくりかえしが、それぞれ、解析されている。

数の並びの構文解析

ここで、例として数の並びの構文解析をしてみる。1文字以上の空白文字で区切られた数値の並びを、数値のリストに変換する。

ひとつの数値を解析する

まずは、ひとつの数値を解析するパーサを定義する。

calc.hs

number :: Parse Integer
number = list1 (check isDigit) `build` read

Haskellでは、多倍長整数としてInteger型の値が使える。関数readは、ここでは、文字列を数値に変換する関数と考えておく。対話環境で試してみよう。

*Main> :reload
*Main> number "4492"
[(4,"492"),(44,"92"),(449,"2"),(4492,"")]
*Main> (number >@ eof) "4492"
[(4492,"")]

パーサeofを最後につけると、残りの文字列が空文字列のものだけにしぼられる。このとき、「残りの文字列」は情報としての価値がなくなる。ということで、タプルの第1要素だけを取り出したい。関数fstが使えると思うが、[(4492,"")]では、タプルはリストのなかにある。

関数map

Haskellでは、関数mapによって、リストの要素すべてに関数を適用できる。

*Main> map negate [3, 4, 5]
[-3,-4,-5]

この関数mapを使うと、つぎのようにできる。

*Main> map fst ((number >@ eof) "4492"
[4492]

関数listToMaybe

ここで、複数の候補のうち、はじめのひとつを取り出すとする。リストの先頭を取り出すのに関数listToMaybeが使える。

*Main> listToMaybe [3, 4, 5]
Just 3
*Main> listToMaybe []
Nothing

空リストでは、値がないことを意味するNothing値がかえる。これを使うと、つぎのようにできる。

*Main> listToMaybe (map fst ((number >@ eof) "4492"))
Just 4492

対話環境に打ち込んだ式listToMaybe ...は、すこし複雑だ。Haskellでは、演算子(.)で関数合成ができる。

*Main> (+ 5) (negate 3)
2
*Main> ((+ 5) . negate) 3
2

関数negateを適用したうえで、関数(+ 5)を適用している。この演算子(.)を使うと、つぎのようにできる。

*Main> (listToMaybe . map fst . (number >@ eof)) "4492"
Just 4492

関数parse

文字列をすべて解析し、結果だけを取り出し、候補のうちの先頭を取り出すという処理を、対話環境で組み立てた。この処理をまとめた関数を定義する。

calc.hs

parse :: Parse a -> String -> Maybe a
parse p = listToMaybe . map fst . (p >@ eof)

対話環境に打ち込んだ式の、変数numberのところを引数pに置き換えたかたちだ。Just値やNothing値の型は、Just値が含む型をaとすると、型Maybe aになる。対話環境で試してみる。

*Main> :reload
*Main> parse number "4492"
4492

区切り用の空白のパース

区切り用の空白をパースするパーサを定義する。

calc.hs

spaces1 :: Parse ()
spaces1 = list1 (check isSpace) `build` const ()

関数isSpaceは空白文字であることを確認する関数だ。空白文字には意味がないので、const ()で、ユニット値に置き換えている。関数constはどんな引数に対しても、おなじ値をかえす関数をつくる関数だ。

数値のリストのパース

「区切リ、数値」のくりかえしのパーサを定義する。

calc.hs

spNumbers :: Parse [Integer]
spNumbers = list (spaces1 @> number)

「1文字以上の空白文字(spaces1)に、数値(number)を続けた(@>)もの」の、0回以上のくりかえし(list)だ。これを使って、数値のリストのパーサを定義する。

calc.hs

numbers :: Parse [Integer]
numbers = (number >@> spNumbers) `build` uncurry (:)

パースしたいのは、「区切り、数値、区切り、数値、...」ではなく、「数値、区切り、数値、区切り、数値、...」なので、はじめに数値(number)を追加した。対話環境で試してみる。

*Main> :reload
*Main> parse numbers "123 456 789"
Just [123,456,789]

ちゃんと解析できている。

当日用資料 4/5へ