Haskell递归调用中traceM输出异常问题求助

问题背景 #

我是Haskell新手，正在学习用Haskell编写编译器，用do语法重写了《Monadic Parser Combinators》里的代码，功能正常，但跟踪word函数执行时，traceM的输出让人困惑：为什么"leave do"出现三次，"enter do"却只出现一次？不管输入字符串多长，"enter do"始终只打印一次——明明word函数被调用了多次。后来在traceM后添加=<< pure，得到了符合预期的跟踪信息，想知道背后的原因。（使用GHC 9.8.2，GHC和GHCi输出一致）

原始代码 #

import Debug.Trace
newtype Parser a = Parser {parse :: String -> [(a, String)]}

zero :: Parser a
zero = Parser $ \_ -> []

item :: Parser Char
item = Parser $ \input -> case input of
                                [] -> []
                                x : xs -> [(x, xs)]

instance Functor Parser where
  fmap f parser = Parser $ \input -> [(f result, input') | (result, input') <- parse parser input]

instance Applicative Parser where
  pure x = Parser $ \input -> [(x, input)]
  p1 <*> p2 = Parser $ \input -> [(mapper result, input'') | (mapper, input') <- parse p1 input, (result, input'') <- parse p2 input']

instance Monad Parser where
  return = pure
  parser >>= f = Parser $ \input -> concat [parse (f result) input' | (result, input') <- parse parser input]

sat :: (Char -> Bool) -> Parser Char
sat predi = item >>= \x -> if predi x then return x else zero

infixl 0 |:
(|:) :: Parser a -> Parser a -> Parser a
p1 |: p2 = Parser $ \input -> parse p1 input ++ parse p2 input 

lower :: Parser Char
lower = sat $ \x -> x >= 'a' && x <= 'z'

upper :: Parser Char
upper = sat $ \x -> x >= 'A' && x <= 'Z'

letter :: Parser Char
letter = lower |: upper

word :: Parser String
word = return "" |: do
  traceM "enter do"
  x <- letter
  traceM $ "x = " ++ show x
  xs <- word
  traceM $ "xs = " ++ show xs
  traceM "leave do" 
  return (x:xs)
main = putStrLn $ show $ parse word "ab"

原始traceM输出 #

enter do
x = 'a'
xs = ""
leave do
x = 'b'
xs = ""
leave do
xs = "b"
leave do

预期输出 #

enter do
x = 'a'
enter do
x = 'b'
xs = ""
leave do
xs = ""
xs = "b"
leave do

修改后traceM输出（添加=<< pure） #

enter do
x = 'a'
xs = ""
leave do
enter do
x = 'b'
xs = ""
leave do
xs = "b"
leave do
enter do

原因解释 #

核心问题：ApplicativeDo扩展的影响 #

GHC默认启用ApplicativeDo扩展，它会将do语法转换为Applicative风格的代码（而非纯Monadic的bind链），这是导致traceM行为不符合预期的关键。

1. 原始代码中traceM的执行时机
   原始do块中的traceM "enter do"是一个无绑定的语句，在ApplicativeDo的处理下，它会被转换为Applicative的(*>)操作：先执行traceM的IO副作用，再执行后续的Parser逻辑。但这个IO副作用只会在Parser值被构造时执行一次——也就是程序启动时定义word函数的那一次，而非每次解析输入、进入该分支时执行。

   而leave do位于xs <- word之后，属于Monadic bind链的一部分，每次完成递归解析后都会触发，因此会打印多次。

2. 修改后代码的作用
   当把traceM "enter do"改为traceM "enter do" =<< pure ()时，相当于手动构造了一个Monadic bind操作：pure () >>= \_ -> traceM "enter do"。这强制将traceM的副作用嵌入到Monadic的bind链中，使得每次解析进入该分支时，都会执行这个trace操作，从而符合预期地多次打印"enter do"。

补充说明 #

• Parser类型并未实现MonadIO实例，原始代码中traceM能通过编译，是因为ApplicativeDo将其与Parser的Applicative实例结合，把IO动作当作Applicative序列的一部分执行。
• word的递归定义return "" |: do ...会尝试两个分支：空字符串或非空单词。每次递归调用word时，只有非空分支会触发do块逻辑，但原始的traceM仅在初始构造时执行一次，因此只出现一次"enter do"。

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