parsing - 是否可以使用applicative来表达chainl1？

Question

是否可以不使用 Parsec 定义的 Monad 实例来表达 Parsec 的 chainl1 组合器？

chainl1 p op =
  do x <- p
     rest x
  where
    rest x = do f <- op
                y <- p
                rest (f x y)
          <|> return x

Answer 1

是的，是:

chainl1 p op = foldl (flip ($)) <$> p <*> many (flip <$> op <*> p)

这个想法是你必须解析 p (op p)*并将其评估为(...(((p) op p) op p)...) 。

稍微扩展一下定义可能会有所帮助:

chainl1 p op = foldl (\x f -> f x) <$> p <*> many ((\f y -> flip f y) <$> op <*> p)

作为 op 的对和p被解析，结果立即应用，但因为 p是 op 的右操作数，它需要 flip .

因此，结果类型为 many (flip <$> op <*> p)是 f [a -> a] 。然后，该函数列表从左到右应用于初始值p。通过foldl .