top page > computer > haskell > web_lecture > for_programmer > parser_list.html
更新日:
文責: 重城良国

リストのパース

はじめに

さて準備はできた。注目!ここはすごいよ。

相互再帰

再帰は「自身を呼ぶ」。相互再帰は「互いを呼びあう」。相互再帰のシンプルで美しい例だ。

パーサをリストのパーサに

ひとつの要素をパースするパーサを複数の要素をパースしてリストとして返すパーサにする。ポイントは0個以上のリストをパースするパーサと1個以上のリストをパースするパーサを同時に作ることだ。

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

`build` uncurry (:)の部分は(x, xs)のようなタプルをx : xsのようにしてリストにしているだけだ。これを消して

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

として考える。ある要素の0個以上のリストは「0個のリストまたは1個以上のリスト」だ。ある要素の1個以上のリストは「ある要素に0個以上のリストを続けたもの」だ。筋が通っている。

文字列を与えてみる。パーサpが失敗したときパーサlist1 pによる候補は空だ。これが基底だ。パーサpが文字をひとつ以上消費するならばp >*> list pのlist pの扱う文字列の長さは減少する。よって基底に近づく。

再帰関数は「筋が通っ」ていて、かつ、再帰のたびに「基底に近づく」ならば問題のない定義だ。これらの関数はパーサpが文字を1文字以上消費するならば問題なく動作する。

動作

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

まとめ

単一要素のパーサをリストのパーサにする関数は相互再帰の美しい例だ。

「パーサ: 基本的な関数」へもどる 「数の並びのパース」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics