Haskell 中单子上下文下无限列表的惰性

Question

我目前是第一次学习 Haskell，在理解惰性求值方面遇到很多困难。

主要问题是，在以下场景中，有些行为是懒惰的，有些则不是，我无法解释为什么他们会这样做。

我将使用的 Monadic 迭代或

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 -- Fine
  

  以上适用于任何单子（至少从我的实验来看）。

• 场景2

  something :: Product [Int]
  something = iterateM return 5
  take 5 <$> something -- Fine
  

  以上适用于 Identity、Sum 等。

• 场景3

  something :: IO [Int]
  something = iterateM return 5
  take 5 <$> something -- Infinite Loop !
  

  上面用List、Maybe等无限循环

我做了一些其他实验，涉及

unsafePerformIO

在计算特定值时进行打印，最终怀疑

fmap

某些函子的实现需要完全计算右侧，这打破了惰性。然而，当我明确地将 fmap 与

take 5

一起应用时，为什么

场景 1

不会无限循环呢？为什么

IO

monad 会出现这种情况？

那么，为什么上述场景会这样呢？

Answer 1

要了解何时定义递归函数，请将其所有递归调用替换为

undefined

并查看结果是否为

undefined

（或无限循环或其他错误）（在这种情况下，递归函数为

undefined

） ，或一些可能的部分值（在这种情况下，递归函数至少是这样定义的）。

iterate f v

在

iterate f v'

（和

<$>

）下对

>>=

进行递归调用。是否如此定义取决于

<$>

（和

>>=

）的严格性（惰性），也就是说，以下等式是否成立：

f <$> undefined = undefined

对于

Identity

（与

Sum

和

Product

相同），如果函数参数是非严格的，则

<$>

是非严格的。 （

Identity

构造函数是一个newtype构造函数，运行时不存在，因此不影响严格性。）

f <$> Identity x = Identity (f x)

让我们评估一下

iterate return 5

。下面的前两步不依赖于 monad（第一步只是展开定义，第二步是 monad 法则）：

iterate return 5
  = return 5 >>= \v -> ((v :) <$> iterate return v)
  = (5 :) <$> iterate return 5

为了判断是否已定义，我们将右侧的

iterate

的递归调用替换为

undefined

。

(5 :) <$> undefined

对于

Identity

，这是一种新类型，

undefined = Identity undefined

（

Identity

模式不会强制其内容。）

(5 :) <$> undefined = (5 :) <$> Identity undefined = Identity (5 : undefined)

因此

iterate return 5

至少等于

Identity (5 : undefined)

。通过将

iterate return 5

替换为该部分结果而不是

undefined

，然后重复，可以获得进一步的近似值。

相比之下，

IO

有严格的

<$>

：

undefined :: IO a

是一个崩溃程序，应用

<$>

只会产生另一个崩溃程序。

iterate return 5 = (5 :) <$> iterate return 5

将对

iterate

的递归调用替换为

undefined

((5 :) <$> undefined) = undefined

因为

<$>

对于

IO

是严格的。因此

iterate return 5 :: IO [Int]

是

undefined

。

Answer 2

主要问题是

>>=

，具体取决于它的作用。对于

Product

，

Monad

实例实现为：

instance Monad Product where
    m >>= k  = k (getProduct m)

因此

iterateM f v = go (getProduct (Product v))
  where go v' = (v' :) <$> iterateM f v'

我们可以远程调用

Product

和

getProduct

函数，因为它们只是从数据构造函数中包装和解开它。

iterateM f v = go v
  where go v' = (v' :) <$> iterateM f v'

或者这样：

iterateM f v = go
  where go = (v' :) <$> go

因此它将在

v'

中包含的列表前面添加一个

go

。对于

Product

来说，右侧是什么并不重要：我们知道它只能是一个乘积，而且我们也不需要计算

Product

中包含的值，因为我们只需要保留函数调用即可（此处

(v' :)

）可能仍需要评估的值。

这意味着对于包含未定义值的

Product

，甚至是

undefined

产品，我们得到：

(take 1 . (0:) <$> (undefined :: Product [Int]))
Product {getProduct = [0]}

现在对于

IO

来说，情况并非如此，

IO

是一个 monad，它也被精确定义为以特定顺序运行事物：因此它可以防止在第一个字节之前将第二个字节写入文件，因为惰性求值以某种方式首先评估第二个：它的主要功能是保证评估顺序（仅针对 IO 操作）保持不变。

但是对于

IO

来说，这意味着如果你有

f v >>= go

，它将首先运行

f v

和然后

go

，并且由于

go

最终是另一个

f v >>= go

，因此你可以继续生产在计算结束之前执行的操作，因此陷入无限循环。