chainl
左結合になる
右結合にしたければchainrを使えばいい
よくあるExpr + Expr + Exprのような連続する二項演算子をパースするparserを作成できる
chainl
chainl :: Parser a -> Parser (a -> a -> a) -> a -> Parser a
chainl1
chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
第1引数
Parser a
第2引数
Parser (a -> a -> a)
演算子を消化して二分木を合成する関数を返すパーサを
内部実装の解説
全然理解していないmrsekut.icon
抽象化がすごいので理解したい
実装例
以下の例は、書き換え前は右結合で、書き換え後は左結合になっているので、例としてはあまり良くない
code:hs
- add ::= term | term ('+' add | "-" add)
-- 書き換え前
add :: Parser Expr
add = do
t <- spaces *> term
spaces
*> (Add t <$> (char '+' *> spaces *> add))
<|> (Sub t <$> (char '-' *> spaces *> add))
<|> pure t
-- 書き換え
add :: Parser Expr
add = term chainl1 addop
addop :: Parser (Expr -> Expr -> Expr)
addop = Add <$ char '+' <|> Sub <$ char '-'
実際にループを使ったものとchainlを使ったものを比較している記事はこれを参考 参考
実装例など、わかりやすい