Parser封装调用差异解析：原liftA2引发栈溢出的原因

问题背景 #

基于Haskell实现Parser类型及相关运行函数时，最初的liftA2直接解构第二个Parser参数为(MkParser pb)，结合many/some组合子运行runParser (some anyChar) "11test"会触发栈溢出。改用unParser调用第二个Parser后问题解决，核心疑问：两种写法逻辑看似一致，为何出现栈溢出？二者差异是什么？

相关代码 #

Parser类型定义 #

data Parser a = MkParser (String -> Maybe (String, a))

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

runParser :: Parser a -> String -> Maybe a
runParser (MkParser pa) inp  = case pa inp of
    Nothing -> Nothing
    Just (cs, c) -> Just c

原liftA2实现（会栈溢出） #

liftA2 :: (a -> b -> c) -> Parser a -> Parser b -> Parser c
liftA2 op (MkParser pa) (MkParser pb) = MkParser sf
    where
        sf inp = case pa inp of
            Nothing -> Nothing
            Just (as, a) -> case pb as of
                Nothing -> Nothing
                Just (bs, b) -> Just (bs, op a b)

修改后的liftA2实现（解决栈溢出） #

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)

差异与原因解析 #

两种写法的核心区别在于Parser构造器的解构时机，而这直接触发了Haskell惰性求值机制的不同表现：

1. 原实现的问题：提前强制解构，打破惰性 #

原liftA2在参数列表中直接对第二个Parser做模式匹配(MkParser pb)——这意味着当调用liftA2时，必须立即解构传入的第二个Parser参数，取出内部的函数pb。

以some anyChar为例，some的定义通常是：

some p = (:) <$> p <*> some p

这里的<*>是基于liftA2实现的。当构建some p时，原liftA2会立即解构递归调用的some p，相当于强制展开递归结构。每一层递归都需要先解析下一层的Parser构造器，导致递归调用被严格求值，栈帧会持续堆积，最终引发栈溢出。

2. 修改后实现的优势：延迟解构，保留惰性 #

修改后的liftA2将第二个Parser参数p2完整保留，直到在内部函数g中通过unParser p2 middle才去解构它。这意味着：

• 解构操作被延迟到了实际需要运行Parser的时刻，而非liftA2被调用的时刻。
• 递归调用的展开是按需进行的：只有当解析完当前字符后，才会触发下一次some p的解析，栈帧不会一次性堆积，而是逐步复用或释放，从而避免了栈溢出。

本质差异 #

两种写法在严格求值语言中逻辑完全一致，但Haskell的惰性求值特性放大了解构时机的影响：

• 原写法的模式匹配发生在参数绑定阶段，属于严格解构，强制递归提前展开。
• 修改后的写法将解构延迟到函数执行阶段，保留了惰性求值，让递归调用按需展开。

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