1日9時間寝たい

本当は10時間寝たいです

FParsec の使い方メモ

はじめに

この問題 を FParsec で解いたので使い方をメモ。

問題概要としては

1 plus 2 plus 3 plus 4

のような入力から 10 を得たい、というもの。

FParsec

F# のパーサコンビネータライブラリです。「string を parse する」「integer を parse する」などの部品が組み合わせやすい形で用意されていて、いちから自分で再帰下降するより (慣れれば) 速くパーサを作れます。

日本語の資料では

が詳しい。

英語でもよいなら、最初に チュートリアル を読んで詳しいところは リファレンス を漁るのがいいと思います。

結果

最終的なソースコードです: https://gist.github.com/ia7ck/ade36d8f909c429a9034b04c9cec8ca8

詳しい実行手順は下のほうに書きます。(書きました: 実行手順)

数値の parse

数値を parse するところから始めましょう。pfloat が使えます。

この関数はパーサを返して、その型は Parser<float,'u> です。1 つ目の型引数 float がパースして得られる値の型です。パースを実行するには run に parser と入力文字列を渡します。何度も使うので実行結果を確認しやすいように以下に示す test を用意しておきましょう (チュートリアルに出てくるものとまったく同じです) 。

let test p str =
    match run p str with
    | Success(result, _, _)   -> printfn "Success: %A" result
    | Failure(errorMsg, _, _) -> printfn "Failure: %s" errorMsg

詳しい説明は省きますが、パースに成功すると Success: ... の形で結果が出力されて、失敗すると Failure: ... と出力されます。

test pfloat "1.23" // Success: 1.23
test pfloat "a1b2c3" // Failure
空白の parse

数値をパースできるようになりましたが、このままでは少し使い勝手が悪いです。先頭に空白があるとパースに失敗してしまいます。

test pfloat "  1.23   " // Failure

前後の空白を消費するように変更しましょう。中置演算子 (二項演算子) (>>.), (.>>) が使えます。p1 >>. p2 も p1 .>> p2 も p1 → p2 の順でパーサを適用しますが、run を実行して得られる結果は . がある側です。ドットが無い側のパース結果は無視です。

連続する空白をパースするには spaces が使えます。

// Parser<float,unit>
let number = spaces >>. pfloat .>> spaces
test number "1.23" // Success: 1.23
test number "  1.23   " // Success: 1.23

number の型は pfloat と同じで Parser<float, 'u> であることに注意してください。

文字列の parse

次は plus をパースすることを考えます。Parser<string,'u> を返す pstring が使えそうです。いいえ、plus をパースして文字列の "plus" が得られても何もうれしくありません。私たちは足し算をしたいのでパース結果は足し算を表す関数: 引数が float, float で返り値が float になるべきです。

// float -> float -> float
let plus (a: float) (b: float) = a + b

stringReturn は stringReturn str result の形で使えます。文字列 str をパースし Parser<resultの型, 'u> を返します。

// Parser<(float -> float -> float), unit>
let opPlus = spaces >>. stringReturn "plus" plus .>> spaces
足し算の parse

数値・plus・数値 の順にパースすればよいです。ただし >>. や .>> は適しません。p1 >>. p2 は p1 のパース結果を捨ててしまうからです。それぞれのパース結果を利用して新しいパーサを返すには pipe3 を使います。

// Parser<float,unit>
let xPlusY = pipe3 number opPlus number (fun x op y -> op x y)
test xPlusY "1 plus 2" // Success: 3.0
test xPlusY "1 plaz 2" // Failure

pipe3 p1 p2 p3 f は p1, p2, p3 をパースしてその結果を f に渡します。f では 1 plus 2 を plus(1, 2) のように並び替えればよいです。

足し算の parse (複数回)

ここまでで 1 回の足し算をパースして計算結果を得ることはできました。最後のステップです。私たちは (ちょうど 1 回ではなく) 好きな回数だけ足し算を実行したいです。そのためには次の形の入力をパースする必要があります。

  • 1
  • 1 plus 2
  • 1 plus 2 plus 3
  • 1 plus 2 plus 3 plus 4
  • ...

このような p (op p)* のパターンには chainl1 が使えます。これは p によるパース結果の列を op で左から fold した値を持つパーサを作ります。たとえば 1 plus 2 plus 3 plus 4 から plus(plus(plus(1, 2), 3), 4) を計算します。

let manyPlus = chainl1 number opPlus
test manyPlus "1 plus 2 plus 3 plus 4" // Success: 10.0

できました！

実行手順

手元で実行してみたい人向けです。