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

Question

考虑以下两个几乎相同的功能:

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

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

Haskell的懒惰方面允许buildList在内存中生成列表而没有太多开销,因为它生成列表的头部然后构建尾部.

但monadic版本buildListM似乎使用更多的内存,n因为它必须首先构建尾部然后在头部前面.

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

Answer 1

许多Monads(例如,IO严格ST s,严格State s)是"严格的",因为>>=它的左操作数是严格的.其他的,最主要的是Identity也(->) a,懒State s,懒Writer q,懒ST s,在这个意义上,"懒" >>=是不是在它的左操作数严格.考虑申请toListM的Identity单子:

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在Identitymonad中运行时相同.特别是monad,而不是monadic性质,使事情变得严格.

你有时可以用两种方式之一在"严格"的monad中做懒惰的事情:

1. 使用unsafeInterleaveIO或作弊unsafeInterleaveST.

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