实现`Applicative Parser`的应用功能

Question

从Brent Yorgey的2013 Penn 课程中,在获得有关定义Functor Parser的帮助之后,我试图制作一个Applicative Parser:

--p1 <*> p2 represents the parser which first runs p1 (which will
--consume some input and produce a function), then passes the
--remaining input to p2 (which consumes more input and produces
--some value), then returns the result of applying the function to the
--value

这是我的尝试:

instance Applicative (Parser) where
  pure x                    = Parser $ \_ -> Just (x, [])
  (Parser f) <*> (Parser g) = case (\ys -> f ys) of Nothing      -> Parser Nothing
                                                    Just (_, xs) -> Parser $ g xs

但是,我在apply (<*>)定义上遇到了编译时错误.

直觉上,我相信使用<*>实现了AND功能.

如果我有一个解析器foo和一个解析器bar,那么我应该可以用apply <*>来说:foo然后bar.换句话说,输入foobar应该成功匹配,而foobip不是.它会在第二个解析器上失败.

但是,我相信这些类型是:

Parser (a -> b) -> Parser a -> Parser b

所以,这让我觉得我的直觉并不完全正确.

请给我一个提示,指导我了解如何实施apply.

Answer 1

您的代码基于对什么Parser是误解.别担心,几乎每个人都犯了这个错误.

newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }

让我们分解这意味着什么.

String -> Maybe (a, String)
[1]       [2]   [3] [4]

[1]:我拿一根绳子然后回来 Maybe (a, String)

[2]:我可能无法成功将输入解析为所需的数据类型

[3]:所需的类型我解析字符串进

[4]:在消耗了解析所需的数据量之后的剩余输入 a

Parser是文本输入的函数,可能是值的元组和文本的其余部分.Parser重点不是元组,否则你就没有解析器.只是元组中的数据.

我不打算告诉你如何实施<*>,其他任何人都不应该因为它会剥夺你的体验.

但是,我会告诉你pure,你了解基本模式:

 pure a = Parser (\s -> Just (a, s))

看到？它是s - > Maybe(a,s)的函数.我故意模仿我的术语中的类型变量,使其更加明显.