如何正确地进行递归解析？

Question

我的代码是这样的：

-- my parser, takes a function that takes a string and gives 
-- the suffix and the answer
data Parser a = MkParser (String -> Maybe (String, a))

unParser :: Parser a -> String -> Maybe (String, a)
unParser (MkParser sf1) = sf1

-- gives `a` as the answer, never fails, doesn't change input string
pure :: a -> Parser a
pure a = MkParser (\inp -> Just (inp, a))

-- Choice... if pa fails, try pa2
(<|>) :: Parser a -> Parser a -> Parser a
MkParser sf1 <|> p2 = MkParser g
  where
    g inp = case sf1 inp of
              Nothing -> unParser p2 inp
              j -> j        -- the Just case

-- | 0 or more times, collect the answers into a list.
many :: Parser a -> Parser [a]
many p = some p <|> pure []
-- Explanation: To repeat 0 or more times, first try 1 or more
-- times!  If that fails, then we know it's 0 times, and the answer is the
-- empty list.

-- | 1 or more times, collect the answers into a list.
some :: Parser a -> Parser [a]
some p = liftA2 (:) p (many p)
-- Explanation: To repeat 1 or more times, do 1 time, then 0 or more times!

liftA2 :: (a -> b -> c) -> Parser a -> Parser b -> Parser c
liftA2 op (MkParser sf1) p2 = MkParser g
  where
    g inp = case sf1 inp of
              Nothing -> Nothing
              Just (middle, a) ->
                  case unParser p2 middle of
                    Nothing -> Nothing
                    Just (rest, b) -> Just (rest, op a b)

我用这个基本解析器测试代码，如果它是我正在寻找的

char

，它就会成功：

char :: Char -> Parser Char
char wanted = MkParser sf
  where
    sf (c:cs) | c == wanted = Just (cs, c)
    sf _ = Nothing

要运行解析器，我使用这个

runParser :: Parser a -> String -> Maybe a
runParser (MkParser sf) inp = case sf inp of
                                Nothing -> Nothing
                                Just (_, a) -> Just a

现在我做到了

runParser (many (char '!')) "testing"

并且我得到了

Just ""

。

我正在尝试单步执行代码。首先，

(many (char '!'))

调用

some (char '!')

。

这称为

liftA2 (:) p (many p)

。在这里，

many p

再次调用

liftA2 (:) p (many p)

。这会无限重复，对吗？我是 Haskell 的新手，但我猜由于它的惰性评估，它最终会尝试评估

p

？。

runParser (char '!') "testing"

给出

Nothing

，因此第一个

liftA2 (:) p (many p)

也给出

Nothing

，对吧？这将转移到

some p <|> pure []

的第二种情况，并且

pure []

给出

Just []

。所以答案应该是

Just []

。

但是当我跑步

runParser (many (char '!')) "Testing"

时得到的答案是

Just ""

。

""

从哪里来？

Answer 1

请注意，

""

与

[]

相同。

Char

的空列表被专门打印为空字符串

""

。