1

パーサー・コンビネーター・ライブラリーの構築に関するチュートリアルを読んでいて、よくわからない方法に出くわしました。

newtype Parser a = Parser {parse :: String -> [(a,String)]}

chainl :: Parser a -> Parser (a -> a -> a) -> a -> Parser a
chainl p op a = (p `chainl1` op) <|> return a

chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
p `chainl1` op = do {a <- p; rest a}
  where rest a = (do f <- op
                     b <- p
                     rest (f a b))
                 <|> return a

bind :: Parser a -> (a -> Parser b) -> Parser b
bind p f = Parser $ \s -> concatMap (\(a, s') -> parse (f a) s') $ parse p s

これは、オペレーターbindの実装です。関数(>>=)の仕組みがよくわかりません。chainl1私が見ることができるものfからop、抽出してから適用してf a b再帰しますが、タプルのリストを返す必要があるときにパーサーから関数を抽出する方法がわかりませんか?

4

1 に答える 1

1

の定義を見ることから始めますParser。

newtype Parser a = Parser {parse :: String -> [(a,String)]}`

AParser aは実際には (後で で実行できる) 関数の単なるラッパーであり、parseを取り、Stringペアのリストを返します。各ペアにはa、文字列の処理中に発生した と、処理されていない残りの文字列が含まれます。 .

chainl1ここで、あなたを混乱させるコードの部分を見てください:fから抽出する部分op:

f <- op

あなたは次のように述べています。

文字列で a を ( を使用して)実行すると、結果として型のリストが得られるのは事実です。しかし、このコードには. むしろ、ここでは (do 記法構文シュガーを使用して) 使用しています。問題は、データ型の定義については考えていますが、具体的に何をするかについてはあまり考えていないことです。Parser aparse[(a,String)]parse op sbindParserbind

bindモナドで何をしているのかをParserもう少し注意深く見てみましょう。

bind :: Parser a -> (a -> Parser b) -> Parser b
bind p f = Parser $ \s -> concatMap (\(a, s') -> parse (f a) s') $ parse p s

何をしp >>= fますか？Parserこれは、string が与えられると、次のことを行う を返しますs。まず、解析する文字列でパーサーを実行します。あなたが正しく指摘したように、これは type のリストを返します。つまり、検出された type の値のリストと、各値が検出された後に残った文字列が返されます。次に、このペアのリストを取得し、各ペアに関数を適用します。具体的には、このリストの各ペアは、(1)解析された値に適用し(新しいパーサーを返します)、(2)この新しいパーサーを残りの文字列で実行することによって変換されます。これはタプルからタプルのリストへの関数です:ps[(a, String)]a(a, s')faf as'(a, s') -> [(b, s'')]...そして、 によって返された元のリスト内のすべてのタプルにこの関数をマッピングしているためparse p s、タプルのリストのリストが得られます: [[(b, s'')]]。したがって、このリストを単一のリストに連結 (または結合) します[(b, s'')]。全体として、関数 from sto[(b, s'')]があり、それをParsernewtype でラップします。

重要な点はf <- op、 またはによって解析された値op >>= \f -> ...に名前を割り当てますが、それはタプルのリストではなく、 b/c を実行した結果ではないということです。fopfparse op s

一般に、いくつかの datatype を定義する多くの Haskell コードと、多くの汚れた詳細を隠して、次のように do 表記を使用して関心のある値にアクセスできるようにSomeMonad aするメソッドが表示されます。 . 舞台裏でどのように状態を通過するかを見るためにモナドを見ることは有益かもしれません。同様に、ここでパーサーを組み合わせる場合、パーサーが認識するはずの値を最も気にします... type の値を認識したときに残る文字列を含むすべての汚い作業を隠しています。bindaa <- maState abindbinda

于 2016-08-17T03:37:48.387 に答える