haskell - 如何在 monad 中懒惰地构建 Haskell 列表？

Question

考虑以下两个几乎相同的函数:

buildList 0 = []
buildList n = n : buildList (n - 1)

buildListM 0 = return []
buildListM n = buildListM (n - 1) >>= return . (n :)

Haskell 的惰性方面允许 buildList生成列表而不会在内存中产生太多开销，因为它会生成列表的头部，然后构建尾部。

但是一元版本 buildListM似乎使用更多内存作为 n变大是因为它必须先构建尾部，然后再添加头部。

这是在 monad 中构建列表的好方法，还是有更有效的方法？

Answer 1

许多 Monads (例如， IO ，严格的 ST s ，严格的 State s )是“严格的”，因为 >>=其左操作数是严格的。其他，最值得注意的是 Identity还有(->) a , 懒惰 State s , 懒惰 Writer q , 懒惰 ST s , 在 >>= 的意义上是“懒惰的”其左操作数不严格。考虑申请toListM在 Identity单子(monad):

buildListM 0 = return []
buildListM n = buildListM (n - 1) >>= return . (n :)

在这里， return = Identity和 Identity m >>= f = f m ， 所以

buildListM 0 = Identity []
buildListM n = Identity . (n :) $ runIdentity (buildListM (n - 1))
             = Identity (n : runIdentity (buildListM (n - 1)))

由于 Identity和 runIdentity在运行时完全无操作， buildListM实际上与 buildList 相同在 Identity 中运行时单子(monad)。使事情变得严格的是特定的单子(monad)，而不是单子(monad)的本性。

您有时可以通过以下两种方式之一在“严格” monad 中做懒惰的事情:

使用 unsafeInterleaveIO 作弊或 unsafeInterleaveST .

使用更强大的MonadFix抽象，它可以让你在计算结果被执行之前掌握它，但是如果你在它可用之前访问这样的结果，那你就会失败。