是否可以使用applicative表达chainl1？

Question

是否有可能chainl1从Parsec 表达组合器而不使用parsec定义的Monad实例？

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.