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

Question

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

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]。然后将这个函数列表从左到右应用于pby的初始值foldl。

Answer 2

丑陋但等效的Applicative定义：

chainl1 p op =
    p <**>
    rest
  where
    rest = flip <$> op <*>
           p <**>
           pure (.) <*> rest
        <|> pure id

而不是将左侧参数x显式传递到右侧op，这种应用形式“链”通过提升的组合op器部分应用于其右侧参数（因此） ，然后将最左侧的通孔应用于结果。flip <$> op <*> p(.)p(<**>)rest :: Alternative f => f (a -> a)