haskell - 为什么这个 haskell 代码没有终止

Question

import Control.Monad.State.Lazy

type Queue a = [a]

push :: a -> State (Queue a) ()
push x = state (\xs -> ((),xs++[x]))

pop :: State (Queue a) a
pop = state (\(x:xs) -> (x,xs))

queueManip :: State (Queue Int) Int
queueManip =
  do
    mapM_ push [1..]
    a <- pop
    return a

main :: IO()
main = do
  let (a,_) = runState queueManip []
  print a

mapM_不应该偷懒吗？除了实现队列之外，复杂度不应该是O(1)吗？

因为追加(++)本身是惰性的...

Answer 1

如果我邪恶并使用怎么办

push' :: Int -> State (Queue Int) ()
push' 1052602983 = state $ \_ -> ((), []) -- "Muarhar!"
push' x = state $ \xs -> ((),xs++[x])

然后 mapM Push' [1..] 应该清楚地将状态渲染为 [1052602983, 1052602984 ..]。 pop 产生 1 是错误的。但如果不首先评估十亿个其他数字，mapM 就不可能知道这一点。实际上将它们推送到状态在这里是无关紧要的，而且 push 可能完全懒惰也没关系:mapM 至少必须给它一个机会 在传递单子(monad)程序流程之前检查任何给定的数字。