Haskell解析器many函数惰性缺失原因及修复方案问询

问题分析 #

你实现的极简Haskell解析库中，take 2 <$> many one会消耗全部输入，核心原因在于Parser的设计和many的标准实现逻辑：

• many的标准定义是many p = some p <|> pure []，其中some p = (:) <$> p <*> many p。你的Parser的Alternative实例是提交式的：只有左边的Parser完全失败时，才会尝试右边的分支。
• 因此many one会递归调用some one，直到one无法解析输入（即输入为空），一次性消耗所有输入生成完整的字符列表。take 2 <$> many one是在这个完整列表生成后截取前两个，但此时输入已经被全部消耗，剩余输入自然为空。

而你的atMostN函数通过显式限制解析次数，每一步只消耗一个输入元素，达到次数后立即停止并保留剩余输入，因此能得到预期结果。

惰性断裂的位置 #

惰性断裂发生在many的递归执行阶段：当前Parser的返回类型是一次性的(a, [s])（完整结果+剩余输入），而非惰性的元素流。many one必须完全遍历输入才能生成完整的结果列表，无法在take 2截取前两个元素后停止输入消耗——因为Parser的执行是“全有或全无”的，无法按需生成元素并保留剩余输入。

修改方案：无法仅通过Alternative实例修复 #

仅修改Alternative实例无法恢复预期的惰性，因为问题根源在于Parser的核心设计：它返回一次性结果而非惰性流。要实现按需解析、保留剩余输入的many，可以通过以下两种方式调整：

方案1：自定义按需解析的组合子

如果不想修改Parser结构，可以实现一个带次数限制的takeN组合子，替代take 2 <$> many one的写法：

takeN :: Monoid e => Int -> Parser s e a -> Parser s e [a]
takeN 0 _ = pure []
takeN n p = (:) <$> p <*> takeN (n-1) p

使用时直接调用takeN 2 one，即可得到预期的Right ("01", "23")结果。

方案2：重构Parser为惰性流结构

如果希望实现真正的惰性解析，可以将Parser的返回类型改为惰性流结构，让结果可以按需生成：

data Stream s a = Cons a (Parser s e (Stream s a)) | Nil [s]
newtype Parser s e a = Parser ([s] -> Either e (Stream s a))

这样many p可以生成一个惰性的Stream，take 2只需要取前两个元素，剩余的输入会保留在Stream的后续节点中。但这种修改会涉及所有实例和基础Parser的重构。

总结 #

当前的many之所以无法保留剩余输入，是因为它的贪婪性和Parser一次性返回结果的设计。仅修改Alternative实例无法解决问题，需要通过自定义组合子（如takeN、atMostN）或重构Parser为惰性流结构来实现预期行为。

内容的提问来源于stack exchange，提问作者G. Rodrigues