parsing - 如何在不假设 Monad 的情况下为解析器实现 Applicative 实例？

Question

我不知道如何实现 Applicative此解析器的实例:

newtype Parser m s a = Parser { getParser :: [s] -> m ([s], a) }

不假设 Monad m .我预计只需要假设 Applicative m , 因为 Functor实例只需假设 Functor m .我终于结束了:

instance Functor m => Functor (Parser m s) where
  fmap f (Parser g) = Parser (fmap (fmap f) . g)


instance Monad m => Applicative (Parser m s) where
  pure a = Parser (\xs -> pure (xs, a))

  Parser f <*> Parser x = Parser h
    where
      h xs = f xs >>= \(ys, f') -> 
        x ys >>= \(zs, x') ->
        pure (zs, f' x')

我该怎么做呢？我尝试替换为 >>=手动，但总是在试图减少 join 时陷入困境-- 这也需要Monad .

我也咨询了Parsec ，但即使这样也没有多大帮助:

instance Applicative.Applicative (ParsecT s u m) where
    pure = return
    (<*>) = ap

我问这个问题的原因纯粹是为了自学。

Answer 1

这是不可能的。看看你的内部 newtype :

getParser :: [s] -> m ([s], a)

想必你想通过[s]到 y 的输入在 x <*> y .这正是 Monad m 之间的区别。和 Applicative m :

在 Monad您可以将一个计算的输出用作另一个计算的输入。

在 Applicative ， 你不能。

如果你做了一个有趣的把戏，这是可能的:

Parser x <*> Parser y = Parser $
    \s -> (\(_, xv) (s', yv) -> (s', xv yv)) <$> x s <*> y s

但是，这几乎肯定不是您想要的定义，因为它解析 x和 y在平行下。

修复

您的 ParserT可以是Applicative很容易:

newtype ParserT m s a = ParserT { runParser :: [s] -> m ([s], a) }
-- or, equvalently
newtype ParserT m s a = ParserT (StateT [s] m a)

instance Monad m => Applicative (ParserT m s) where
    ...

请注意 ParserT m s不是 Monad 的实例只要你不定义 Monad实例。

您可以将剩余字符移出解析器:

newtype ParserT m s a = ParserT { runParser :: [s] -> ([s], m a) }

instance Applicative m => Applicative (ParserT m s) where
    ParserT x <*> ParserT y = ParserT $ \s ->
        let (s', x') = x s
            (s'', y') = y s'
        in x' <*> y'
    ...