我试图理解这是怎么回事:
satisfy :: (Char -> Bool) -> Parser Char
satisfy pred = PsrOf p
where
p (c:cs) | pred c = Just (cs, c)
p _ = Nothing
相当于:
satisfy :: (Char -> Bool) -> Parser Char
satisfy pred = do
c <- anyChar
if pred c then return c else empty
这是关于Haskell解析的一些讲义的片段,我试图理解:
import Control.Applicative
import Data.Char
import Data.Functor
import Data.List
newtype Parser a = PsrOf (String -> Maybe (String, a))
-- Function from input string to:
--
-- * Nothing, if failure (syntax error);
-- * Just (unconsumed input, answer), if success.
dePsr :: Parser a -> String -> Maybe (String, a)
dePsr (PsrOf p) = p
-- Monadic Parsing in Haskell uses [] instead of Maybe to support ambiguous
-- grammars and multiple answers.
-- | Use a parser on an input string.
runParser :: Parser a -> String -> Maybe a
runParser (PsrOf p) inp = case p inp of
Nothing -> Nothing
Just (_, a) -> Just a
-- OR: fmap (\(_,a) -> a) (p inp)
-- | Read a character and return. Failure if input is empty.
anyChar :: Parser Char
anyChar = PsrOf p
where
p "" = Nothing
p (c:cs) = Just (cs, c)
-- | Read a character and check against the given character.
char :: Char -> Parser Char
-- char wanted = PsrOf p
-- where
-- p (c:cs) | c == wanted = Just (cs, c)
-- p _ = Nothing
char wanted = satisfy (\c -> c == wanted) -- (== wanted)
-- | Read a character and check against the given predicate.
satisfy :: (Char -> Bool) -> Parser Char
satisfy pred = PsrOf p
where
p (c:cs) | pred c = Just (cs, c)
p _ = Nothing
-- Could also be:
-- satisfy pred = do
-- c <- anyChar
-- if pred c then return c else empty
instance Monad Parser where
-- return :: a -> Parser a
return = pure
-- (>>=) :: Parser a -> (a -> Parser b) -> Parser b
PsrOf p1 >>= k = PsrOf q
where
q inp = case p1 inp of
Nothing -> Nothing
Just (rest, a) -> dePsr (k a) rest
我理解了Monad定义的最后一点,特别是我不明白以下行如何返回Parser b
定义所需的(>>=)
类型:
Just (rest, a) -> dePsr (k a) rest
我很难理解Monad定义在没有示例的情况下的含义。值得庆幸的是,我们在satisfy
函数的替代版本中有一个使用do-notation(当然这意味着调用了Monad)。我真的不明白do-notation,所以这里是satisfy
的desugared版本:
satisfy pred = do
anyChar >>= (c ->
if pred c then return c else empty)
所以基于我们的(>>=)
definition的第一行,即
PsrOf p1 >>= k = PsrOf q
我们有anyChar
作为我们的PsrOf p1
和(c -> if pred c then return c else empty)
作为我们的k
。我没有得到的是在dePsr (k a) rest
中(k a)
如何返回Parser
(至少它被称为,否则在它上面调用dePsr
就没有意义)。由于rest
的存在,这更令人困惑。即使(k a)
返回Parser
,调用dePsr
将从返回的Parser
提取基础函数并将rest
作为输入传递给它。根据Parser b
的定义,这肯定不会返回(>>=)
类型的东西。显然我在某处误解了某些东西。
好吧,也许这会有所帮助。让我们首先回到dePsr
。
dePsr :: Parser a -> String -> Maybe (String, a)
dePsr (PsrOf p) rest = p rest
让我们也写出回报:(注意我为了清晰起见而提出所有要点)
return :: a -> Parser a
return a = PsrOf (\rest -> Just (rest, a))
现在来自Just
定义的(>>=)
分支
Just (rest, a) -> dePsr (k a) rest
让我们确保我们就每件事情都达成一致:
rest
应用p1
后仍保持未解析的字符串a
应用p1
的结果k :: a -> Parser b
获取前一个解析器的结果并创建一个新的解析器dePsr
将Parser a
解包回函数`String - > Maybe(String,a)请记住,我们将在函数顶部再次将其包装回解析器:PsrOf q
所以在英语中绑定(>>=)
将a
中的解析器和a
中的函数转换为b
中的解析器,并返回b
中的解析器。生成的解析器是通过在解析器构造函数q :: String -> Maybe (String, b)
中包装PsrOf
来生成的。然后q
,组合解析器,取一个名为String
的inp
,并将我们从模式匹配得到的函数p1 :: String -> Maybe (String,a)
应用于第一个解析器,并对结果进行模式匹配。对于错误,我们传播Nothing
(简单)。如果第一个解析器有结果我们有两条信息,仍然未解析的字符串叫做rest
,结果是a
。我们将a
提供给k
,第二个解析器组合器,并得到一个Parser b
,我们需要用dePsr
解包来获得一个函数(String -> Maybe (String,b)
回来。该函数可以应用于rest
以获得组合解析器的最终结果。
我认为阅读本文最困难的部分是有时候我们会对解析器函数进行curry,这会模糊实际发生的事情。
好的satisfy
例子
satisfy pred
= anyChar >>= (c -> if pred c then return c else empty)
empty
来自替代实例,是PsrOf (const Nothing)
所以一个总是失败的解析器。
让我们看看成功的分支机构。仅替换成功部分:
PsrOf (\(c:cs) ->Just (cs, c)) >>= (\c -> PsrOf (\rest -> Just (rest, c)))
所以在绑定(>>=)
定义
p1 = \(c:cs -> Just (cs, c))
k = (\c -> PsrOf (\rest -> Just (rest, c)))
q inp = let Just (rest,a) = p1 inp in dePsr (k a) rest
再次成功分支然后q
成为
q inp =
let Just (rest, a) = (\(c:cs) -> Just (cs, c)) inp
in dePsr (\c -> PsrOf (\rest -> Just (rest, c))) a rest
做一点β-减少
q inp =
let (c:cs) = inp
rest = cs
a = c
in dePsr (PsdOf (\rest -> Just (rest, a))) rest -- dePsr . PsrOf = id
最后清理了一些
q (c:cs) = Just (cs, c)
因此,如果pred
成功,我们将satisfy
减少到恰好anyChar
,这正是我们所期望的,正是我们在问题的第一个例子中找到的。我会把它留给读者(并读取:我很懒)来证明如果inp = ""
或pred c = False
结果是Nothing
,就像在第一个satisfy
例子中那样。
注意:如果你正在做除课堂作业以外的任何事情,你将从一开始就使用错误处理来节省你自己的痛苦和挫折时间使你的解析器String -> Either String (String,a)
很容易使错误类型更加通用,但是PITA到改变从Maybe
到Either
的一切。
问题:“[C]你应该解释一下,当你把”积分“归还给你后,你是如何从return a = PsrOf (\rest -> Just (rest, a))
到达return = pure
的吗?
答:首先,在没有Functor和Applicative定义的情况下给出Monad实例定义是非常不幸的。 pure
和return
函数必须相同(它是Monad定律的一部分),除了Monad
远远早于Haskell历史中的Applicative之外,它们将被称为相同的东西。事实上,我并不“知道”纯粹的样子,但我知道它必须是什么,因为它是唯一可能的定义。 (如果你想理解那个陈述的证明问,我已经阅读了论文,我知道结果,但我不是很有信心的lambda演算,而是对再现结果有信心。)
return
必须在上下文中包装一个值而不改变上下文。
return :: Monad m => a -> m a
return :: a -> Parser a -- for our Monad
return :: a -> PsrOf(\str -> Maybe (rest, value)) -- substituting the constructor (PSUDO CODE)
Parser
是一个函数,它接受一个字符串进行解析并返回Just
值以及原始字符串或Nothing on failure, all wrapped in the constructor
PsrOf. The context is the string to be parsed, so we cannot change that. The value is of course what was passed to
return`的任何未解析部分。解析器总是成功所以我们必须返回一个值。
return a = PsrOf (\rest -> Just (rest, a))
rest
是上下文,它通过不变。 a
是我们投入Monad背景的价值。
为了完整起见,这里也是Functor中唯一合理的fmap
定义。
fmap :: Functor f => (a->b) -> f a -> f b
fmap :: (a -> b) -> Parser a -> Parser b -- for Parser Monad
fmap f (PsrOf p) = PsrOf q
where q inp = case p inp of
Nothing -> Nothing
Just (rest, a) -> Just (rest, f a)
-- better but less instructive definition of q
-- q = fmap (\(rest,a) -> (rest, f a)) . p