使用monad进行简单的Haskell解析器

问题描述 投票:2回答:1

TL; DR

我试图理解这是怎么回事:

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的定义,这肯定不会返回(>>=)类型的东西。显然我在某处误解了某些东西。

parsing haskell monads
1个回答
3
投票

好吧,也许这会有所帮助。让我们首先回到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获取前一个解析器的结果并创建一个新的解析器
  • dePsrParser a解包回函数`String - > Maybe(String,a)

请记住,我们将在函数顶部再次将其包装回解析器:PsrOf q

所以在英语中绑定(>>=)a中的解析器和a中的函数转换为b中的解析器,并返回b中的解析器。生成的解析器是通过在解析器构造函数q :: String -> Maybe (String, b)中包装PsrOf来生成的。然后q,组合解析器,取一个名为Stringinp,并将我们从模式匹配得到的函数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到改变从MaybeEither的一切。


问题:“[C]你应该解释一下,当你把”积分“归还给你后,你是如何从return a = PsrOf (\rest -> Just (rest, a))到达return = pure的吗?

答:首先,在没有Functor和Applicative定义的情况下给出Monad实例定义是非常不幸的。 purereturn函数必须相同(它是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 constructorPsrOf. The context is the string to be parsed, so we cannot change that. The value is of course what was passed toreturn`的任何未解析部分。解析器总是成功所以我们必须返回一个值。

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
© www.soinside.com 2019 - 2024. All rights reserved.