10

我不知道如何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

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

4

2 回答 2

12

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

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

大概，您想传递给in[s]的输入。这正是 和 之间的区别：yx <*> yMonad mApplicative 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它就不是实例。MonadMonad

  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'
    ...
于 2012-10-31T20:13:01.700 回答
3

旨在尽可能使用 Applicative 的满分——它更干净。

标题：您的解析器可以保持 Applicative，但您可能的解析集合需要存储在 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!")

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

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

于 2012-11-01T11:14:01.053 回答