如何在不假设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')

我该怎么做呢？我尝试>>=用手代替,但总是因为试图减少a join而陷入困境- 这也需要Monad.

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

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

我提出这个问题的原因纯粹是自我教育.

Answer 1

这是不可能的.看看你的内心newtype:

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

据推测,你想传递[s]给yin 的输入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并行.

修复

1. 你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实例.

2. 您可以在解析器外移动剩余的字符:

   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'
       ...
   

Answer 2

满分是为了尽可能多地使用Applicative——它更干净。

标题：你的解析器可以保持 Applicative，但是你可能的解析集合需要存储在 Monad 中。内部结构：使用monad。外部结构：适用。

您用来m ([s],a)表示一堆可能的解析。当您解析下一个输入时，您希望它取决于已经解析的内容，但您正在使用它，m因为可能存在少于或多于一个可能的解析；你想要做\([s],a) -> ...并与之合作来制作一个新的m ([s],a). 这个过程称为绑定和使用>>=或等效过程，因此您的容器绝对是一个 Monad，无法逃脱。

在容器中使用 monad 并不是那么糟糕 - 毕竟它只是一个用来保存一些东西的容器。内部使用 monad 和成为 monad 之间是有区别的。您的解析器可以在内部使用 monad 时应用。

请参阅应用解析相对于单子解析有什么好处？。

如果您的解析器是适用的，那么它们会更简单，因此理论上您可以在组合它们时进行一些优化，通过保留有关它们所做的事情的静态信息而不是保留它们的实现。例如，

string "Hello World!" <|> string "Hello Mum!"
== (++) <$> string "Hello " <*> (string "World" <|> string "Mum!")

第二个版本比第一个版本更好，因为它没有回溯。

如果你做了很多这样的事情，就像在运行之前编译正则表达式一样，创建一个图（有限状态自动机）并尽可能地简化它，并消除整个低效回溯的负载。