gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-04 03:22:17 26 4
gpt4 key购买 nike

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

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

最佳答案

这是不可能的。看看你的内部 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

    但是,这几乎肯定不是您想要的定义,因为它解析 xy在平行下。

    修复
  • 您的 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'
    ...
  • 关于parsing - 如何在不假设 Monad 的情况下为解析器实现 Applicative 实例?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13166673/

    26 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com