函数 monad 递归调用中 `TraceM` 的输出混乱

Question

我是 Haskell 新手，正在学习如何使用 Haskell 编写编译器。我使用如下所示的 monad 语法在“Monadic Parser Combinators”中重写了这些代码。一切似乎都运行良好，但当我尝试跟踪

traceM

的执行时，我得到了令人困惑的

word

输出。为什么“leave do”出现了3次而“enter do”只出现了一次？ （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

我的预期输出

traceM

如下（我不确定我是否错了）：

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

更新：我知道

<-

不是赋值，它实际上是

bind

的语法糖。更准确地说，我想知道为什么“enter do”总是打印一次（无论输入字符串的长度有多长），因为

word

函数肯定被调用了很多次。

Answer 1

您的解析器类型涉及一个返回

[(a, String)]

的函数，即解析输入字符串的所有可能方法（复数）。

因此，

do x <- parserA ; y <- parserB

与列表理解有点相似

[ ... | x <- parsesOfA , y <- parsesOfB ]

或者，如果您愿意，也可以是一种命令式循环：

for x in parsesOfA:
   for y in parsesOfB:
      ...

如果

parserA

返回多种解析方式，则

parserB

会运行多次。因此，观察到一个“进入”和许多“离开”消息是预期的行为。