Haskell简易单子解析器中的诡异Bug及成因问询

我参考Hutton和Meijer的思路实现了一个简易单子解析器，核心代码如下：

import Control.Applicative
import Data.Char

data Parser a = P (String -> [(String, a)])

parse :: Parser a -> String -> [(String, a)]
parse (P p) = p
  
char :: Parser Char
char = P $ \s -> case s of
  [] -> []
  (c:cs) -> [(cs, c)]
  
instance Functor Parser where
  fmap f (P t) = P $ \s -> [ (s, f a) | (s, a) <- t s ]

instance Applicative Parser where
  pure a = P (\s -> [(s, a)])
  P f <*> P a = P $ \s -> [(s, f a) | (s, f) <- f s, (s, a) <- a s]
    
instance Monad Parser where
  P a >>= pf = P $ \s -> [(s, a) | (s, a) <- a s, let P f = pf a, (s, a) <- f s]

instance Alternative Parser where
  empty = P $ \s -> []
  P a <|> P b = P $ \s -> case a s of
                            [] -> b s
                            r -> r

单个字符解析功能正常，比如执行parse char "abc"会返回[("bc",'a')]，但调用parse (many char) "abc"时会陷入无限循环，无法输出结果。

两种可行的修复方式 #

方式一：修改<|>的定义 #

将Alternative实例中的<|>改为以下形式后，问题解决，parse (many char) "abc"能正常返回[("", "abc")]：

instance Alternative Parser where
  empty = P $ \s -> []
  pa <|> P b = P $ \s -> case parse pa s of
                           [] -> b s
                           r -> r

方式二：修改<*>的定义 #

不改动<|>，仅将Applicative实例中的<*>改为以下形式，同样能修复无限循环问题：

instance Applicative Parser where
  pure a = P (\s -> [(s, a)])
  P f <*> pa = P $ \s -> [(s, f a) | (s, f) <- f s, (s, a) <- parse pa s]

问题成因解析 #

核心原因在于Haskell的惰性求值特性与模式匹配的严格性冲突：

1. 原<|>定义的问题：
   原<|>用了P a <|> P b的模式匹配，这会在构造<|>解析器时，立即对左右两个Parser进行模式匹配，取出它们内部的函数。而many的标准定义是many p = some p <|> pure []，其中some p = (:) <$> p <*> many p。当构造many char时，<|>的模式匹配会强制求值some char对应的Parser内部函数，而some char又依赖many char，这就触发了无限递归展开——程序会不断尝试展开many char的结构，永远无法停止。

   修改后的<|>定义中，左边的pa没有做模式匹配，而是保留为Parser类型，直到调用parse pa s时才会去求值它的内部函数。这利用了惰性求值，只有当实际需要解析字符串时，才会逐步展开many的递归结构，不会提前触发无限循环。

2. 原<*>定义的问题：
   原<*>用了P f <*> P a的模式匹配，同样会对左右两边的Parser做严格匹配。在some p = (:) <$> p <*> many p中，<*>的模式匹配会强制求值many p的内部函数，进而触发无限递归。而修改后的<*>只对左边做模式匹配，右边的pa保留为Parser类型，直到调用parse pa s时才求值，推迟了递归结构的展开时机，自然避免了无限循环。

总结来说，原代码的模式匹配过于严格，提前触发了many的无限递归展开；修改后的定义通过保留Parser的抽象类型，利用惰性求值推迟了递归展开的时机，从而解决了问题。

内容的提问来源于stack exchange，提问作者haskell looks great