Haskell中单子上下文下无限列表的惰性求值问题

本文使用的单子迭代函数iterateM定义如下：

iterateM :: (Monad m) => (a -> m a) -> a -> m [a]
iterateM f v = f v >>= go
  where go v' = (v' :) <$> iterateM f v'

场景1 #

something :: IO [Int]
something = return [1 ..]
take 5 <$> something -- 正常运行

该场景在任意单子中均可正常运行（至少我的实验结果如此）。

场景2 #

something :: Product [Int]
something = iterateM return 5
take 5 <$> something -- 正常运行

该场景在Identity、Sum等单子中均可正常运行。

场景3 #

something :: IO [Int]
something = iterateM return 5
take 5 <$> something -- 无限循环！

该场景在List、Maybe等单子中会陷入无限循环。

我还通过unsafePerformIO做了一些实验，打印值的计算时机，最终猜测部分函子的fmap实现需要完全计算右侧值，从而破坏了惰性。但为何场景1中明明使用了fmap take 5却不会无限循环？为何IO单子也会出现这种情况？

因此，我想知道这些场景为何会有这样的表现？

理解补充（概念性数学层面） #

感谢各位的解答，我现在理解了其中原理，以下是我的概念性理解，供后续参考：

IO类型可等价理解为IO a = World -> (World, a)，大致拆分为两个独立函数：转换函数t :: (World -> World)和结果函数p :: (World -> a)，二者组合为元组。

IO函子的fmap实现 #

其类型签名为(a -> b) -> IO a -> IO b，逻辑是保持转换函数不变，将映射函数f与结果函数p组合作为新的结果函数：

fmap :: (a -> b) -> IO a -> World -> (World, b)
fmap f x world =
  let newT = t
      newP = f . p in
    (newT world, newP world)
  where
    t = fst . x
    p = snd . x

IO单子的join实现 #

join（即μ变换）的类型签名为IO (IO a) -> IO a，等价于(World -> (World, IO a)) -> (World -> (World, a))。实现逻辑是将两次的世界转换函数组合，结果函数则基于第一次转换后的世界来计算：

join :: IO (IO a) -> World -> (World, a)
join x world =
  let newT = t2 . t1
      newP = p2 . t1 in
    (newT world, newP world)
  where
    t1 :: World -> World
    t2 :: World -> World
    p2 :: World -> a
    t1 = fst . x
    p1 = snd . x
    t2 = fst . p1
    p2 = snd . p1

绑定函数>>=的定义 #

基于join，绑定函数可定义为：

=<< :: (a -> IO b) -> IO a -> IO b
=<< = join . fmap

>>= :: IO a -> (a -> IO b) -> IO b
>>= = flip (=<<)

这意味着它的转换函数是第一个参数的转换函数与第二个参数返回值的转换函数的组合。

IO的return实现 #

return（即η变换）逻辑很简单：

return :: a -> World -> (World, a)
return x world =
  let newT = id
      newP = const x
  in (newT world, newP world)

回到场景3的分析 #

重新看iterateM和场景3的代码：

iterateM :: (Monad m) => (a -> m a) -> a -> m [a]
iterateM f v = f v >>= go
  where go v' = (v' :) <$> iterateM f v'

something :: IO [Int]
something = iterateM return 5
take 5 <$> something

something的转换函数是f v的转换函数（即id）与go返回值的转换函数的组合，而go返回值的转换函数又和右侧iterateM f v'的转换函数相同，这就形成了id的无限组合，导致无限循环。

结果函数则是(5 :)与后续结果函数的无限组合，左侧的这种组合本身没问题，但结合转换函数的无限组合就引发了问题。这正对应了“IO是被明确定义为按特定顺序执行操作的单子”——函数按顺序组合以保证IO操作的执行顺序，无限迭代就会形成无限组合。

其他单子的情况 #

• Maybe单子：join函数需要知道右侧是Just还是Nothing，这一特性会破坏惰性，相关特性也被记录为惰性破坏因素。
• List单子：fmap需要知道右侧的第n个元素才能推导返回值的第n个元素，而从代码逻辑来看，它无法推导出任何元素，因此陷入无限循环。

场景1正常运行的原因 #

IO单子本身不会破坏内部值的惰性，场景1中return [1..]的结果函数是const [1..]，fmap take 5只是将take 5与这个结果函数组合，不需要提前计算整个无限列表，因此可以正常运行。

当然，上述代码并非Haskell实际IO的实现方式（无法真正捕获World并在现实世界中执行操作），但从概念层面可以清晰解释问题。

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