如何逐步分析递归解析？Haskell解析器运行流程疑问

实现的解析器代码 #

-- 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 ""，但预期应为Just []，想知道""的来源。同时有以下疑问：

• many (char '!')调用some (char '!')，后者调用liftA2 (:) p (many p)，many p又会递归调用，是否会无限递归？Haskell惰性求值是否会最终尝试计算p？
• runParser (char '!') "testing"返回Nothing，因此第一个liftA2 (:) p (many p)也返回Nothing，随后进入some p <|> pure []的第二个分支，pure []返回Just []，但实际结果为何是Just ""？

我的分析步骤 #

many (char '!') = some (char '!') <|> pure []
-- calls some p
some (char '!') = liftA2 (:) (char '!') (many (char '!'))
-- here, it waits for the third argument of liftA2, or does it
-- start trying to run liftA2 with the second argument?
-- (many (char '!')) calls this:
many (char '!') = some (char '!') <|> pure []
-- which then again calls 
some (char '!') = liftA2 (:) (char '!') (many (char '!'))
-- so now it looks like this:
liftA2 (:) (char '!') ( liftA2 (:) (char '!') (many (char '!')) )
-- When does it start evaluating? 
-- Because `(many (char '!')` can't technically run because
-- it needs to wait for the third argument of 
liftA2 (:) (char '!') (many (char '!'))
-- which never gives an answer since it keeps recursing right?

我的猜测 #

many (char '!') = some (char '!') <|> pure []
some (char '!') = liftA2 (:) (char '!') (many (char '!'))
-- run `liftA2 (:) (char '!')`, get `Nothing`
-- go to the second choice of <|>
<|> pure []
-- give Just []
Just []

另一个测试用例的推导 #

执行runParser (many (char '!')) "!esting"时，我的推导步骤是否正确？

(many (char '!'))
many p = some p <|> pure []
-- calls `some p`
some (char '!') = liftA2 (:) (char '!') (many (char '!'))
-- the first `char !` (second argument) runs, and it is a success.
-- the success gives Just ("esting", '!') to the third
-- argument of liftA2.
-- Now it goes to the third argument of liftA2, which is
(many (char '!')
-- which calls
many p = some p <|> pure [] -- but the string is "esting"
-- this calls
some (char '!') = liftA2 (:) (char '!') (many (char '!'))
-- the string is "esting"
-- this fails, so it tries the second choice of
some p <|> pure []
-- which is `pure []` which just gives []

-- Now we go back to the first
liftA2 (:) (char '!') (many (char '!'))
-- where the first answer is '!' and the second answer is '[]'
-- and it combines it with `:`. So we have
-- Just ("sting", '!' : '[]')

解答 #

1. Just ""与Just []的本质：在Haskell中，String是[Char]的类型别名，空字符串""就是空列表[]。GHCi在显示结果时，会将[Char]类型的值以字符串形式输出，因此Just []会被显示为Just ""——二者是同一个值，你的预期和实际结果没有差异。

2. 递归与求值流程：不会发生无限递归。Haskell的惰性求值特性意味着，只有当需要计算结果时才会展开表达式。当解析"testing"时：

   • some (char '!')调用liftA2 (:) (char '!') (many (char '!'))，首先执行char '!'解析"testing"，返回Nothing，因此整个liftA2的结果是Nothing；
   • <|>运算符捕获到Nothing，转而执行pure []，返回Just ("testing", [])；
   • runParser提取出结果部分，得到Just []（显示为Just ""）。

你的猜测完全正确，执行流程确实是some p失败后进入pure []分支。

3. "!esting"的推导验证：你的推导步骤是正确的。最终解析结果是'!' : []，也就是"!"，runParser会返回Just "!"（或Just ['!']，取决于GHCi的显示形式）。

内容的提问来源于stack exchange，提问作者user20102550