如何实现可零次或多次应用传入Parser的解析函数并保存结果列表？

嘿，我完全懂你现在的困惑——递归收集解析结果确实是写这类基础解析器组合子的第一个小难点，咱们一步步拆解来搞定它。

首先回顾下你的基础定义：

type Parser a = String -> Maybe (a, String)

parseChar :: Char -> Parser Char
parseChar _ [] = Nothing
parseChar c (x:xs) | c == x = Just (x, xs) | otherwise = Nothing

你需要的parse函数（这类组合子在标准解析库中通常叫many，不过咱们就沿用你的命名）核心逻辑是零次或多次重复应用传入的解析器，把每次成功解析的元素收集成列表，关键在于处理两种递归分支：

实现思路 #

1. 分支1：解析失败：如果第一次应用解析器就返回Nothing，说明没有可解析的元素，此时返回空列表和原字符串（对应「零次应用」的情况）。
2. 分支2：解析成功：如果解析得到了一个元素x和剩余字符串s'，就递归调用parse处理s'，得到后续元素的列表xs，最后把x放到xs的开头，组合成完整的结果列表。

代码实现（显式case版本） #

这个版本更直观，适合理解递归逻辑：

parse :: Parser a -> Parser [a]
parse p input = case p input of
    -- 解析失败，返回空列表和原输入字符串
    Nothing -> Just ([], input)
    -- 解析成功，递归处理剩余字符串并拼接结果
    Just (x, remaining) -> case parse p remaining of
        Just (xs, finalRemaining) -> Just (x : xs, finalRemaining)

更简洁的Do语法版本（可选） #

如果你了解Haskell的Monad，可以给Parser定义Monad实例（或者直接利用Maybe的Monad特性），用do语法让代码更清爽：
首先补全Parser的Functor和Monad实例（这是使用do语法的前提）：

instance Functor Parser where
    fmap f p = \s -> case p s of
        Nothing -> Nothing
        Just (a, s') -> Just (f a, s')

instance Applicative Parser where
    pure x = \s -> Just (x, s)
    pf <*> pa = \s -> case pf s of
        Nothing -> Nothing
        Just (f, s') -> case pa s' of
            Nothing -> Nothing
            Just (a, s'') -> Just (f a, s'')

instance Monad Parser where
    return = pure
    p >>= f = \s -> case p s of
        Nothing -> Nothing
        Just (a, s') -> f a s'

然后parse函数可以写成：

parse :: Parser a -> Parser [a]
parse p = do
    result <- p
    case result of
        Nothing -> return []
        Just x -> do
            xs <- parse p
            return (x : xs)

验证你的示例 #

运行你给出的测试用例：

parse (parseChar ' ') " foobar"

执行流程是：

1. 第一次调用parseChar ' '处理" foobar"，得到Just (' ', "foobar")
2. 递归调用parse (parseChar ' ')处理"foobar"，此时parseChar ' '返回Nothing，所以递归分支返回Just ([], "foobar")
3. 拼接结果得到Just (' ' : [], "foobar")，也就是你预期的Just (" ", "foobar")

额外的边界情况测试 #

• 空输入：parse (parseChar 'a') "" → Just ([], "")（零次应用合法）
• 多次匹配：parse (parseChar 'a') "aaab" → Just ("aaa", "b")

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