Haskell的评估和空间泄漏

Question

我正在学习Haskell,目前正试图绕着monads.在玩一些随机数字时,我再一次被懒惰的评价绊倒了.为了简化以下内容:

roll :: State StdGen Int
roll = do
    gen <- get
    let (n, newGen) = randomR (0,1) gen
    put newGen
    return n

main = do
    gen <- getStdGen
    let x = sum $ evalState (replicateM iterations roll) gen
    print x

进入这样的事情:

roll' :: IO Int
roll' = getStdRandom $ randomR (0,1)

main = do
    x' <- fmap sum $ replicateM iterations roll'
    print x'

更多的iterations,比方说1000 * 1000 * 10,第二个例子会导致堆栈溢出.

为什么第一个版本在恒定空间中快乐地运行而第二个版本爆炸？

更广泛地说,你能推荐一些阅读来改善Haskell懒惰评估的心理模型吗？(介绍中级,最好是.)因为在Haskell的评估中,我的直觉完全让我失望.

Answer 1

罪魁祸首深藏在内心深处replicateM.让我们来看看来源.

replicateM        :: (Monad m) => Int -> m a -> m [a]
replicateM n x    = sequence (replicate n x)

sequence       :: Monad m => [m a] -> m [a] 
sequence ms = foldr k (return []) ms where
  k m m' = do { x <- m; xs <- m'; return (x:xs) }

特别是,看看在单个展开foldr的sequence

foldr k (return []) (replicate n roll')

do x  <- roll'
   xs <- foldr k (return []) (replicate n roll')
   return (x:xs)

换句话说,除非我们可以懒得(x : ... thunk ... )早退,否则我们将在返回第一个值之前展开整个复制.关于我们是否可以返回该值的答案与(>>=)我们monad中的定义有关.

roll' >>= \x -> foldr k (return []) (replicate n roll') >>= \xs -> return (x:xs)

可以说,由于IO执行副作用,它将按顺序执行 - 我们肯定会展开整个事情.State有两种形式,该Control.Monad.Trans.State.Lazy版本与Control.Monad.Trans.State.Strict版本,其中Control.Monad.Trans.State默认的Lazy版本.在那里,(>>=)被定义为

m >>= k  = StateT $ \s -> do
    ~(a, s') <- runStateT m s
    runStateT (k a) s'

所以我们可以看到显式的无可辩驳的绑定发生,这让我们继续懒惰地返回结果.

值得一看的是Joachim Breitner最近对这个问题的评论.还有在这大量的工作中pipes,并conduit可能是值得研究的生态系统.

一般来说,值得怀疑的replicateM是,由于我们在上面看到的排序概念:"构建头部然后构建尾部然后返回缺点".

Answer 2

这是因为Control.Monad.State再出口Control.Monad.State.Lazy.如果你导入了,Control.Monad.State.Strict两者都会溢出.

它之所以具有严格的溢出State或者IO是replicateM需要运行的操作iterations递归时间,才可以建立的名单.松散地说,replicateM必须将它复制的所有行动的"效果""结合"成一个巨大的"效果".术语"结合"和"效果"非常模糊,可能意味着无数不同的东西,但它们是我们谈论这些抽象事物时最好的.replicateM具有较大的值将最终在几乎所有monad选项中溢出堆栈.这是事实,它不是懒惰State,这是奇怪的.

要了解为什么它不会溢出懒惰State,你需要查看(>>=)懒惰的细节State,和replicateM.以下定义大大简化,但它们反映了说明其工作原理所需的详细信息.

newtype State s a = State { runState :: s -> (a, s) }

instance Monad (State s) where
    return x = State $ \s -> (x, s)
    x >>= f = State $ \s -> let (a, s') = runState x s in runState (f a) s'

replicateM :: Monad m => Int -> m a -> m [a]
replicateM 0 _ = return []
replicateM n mx | n < 0 = error "don't do this"
                | otherwise =
                    mx >>= \x -> replicateM (n - 1) mx >>= \xs -> return (x:xs)

首先,看看replicateM.请注意,当n大于0时,它是一个调用(>>=).所以行为replicateM取决于什么(>>=).

当您查看时(>>=),您会看到它生成状态转换函数,该函数x在let绑定中绑定状态转换函数的结果,然后返回转换函数的结果,该结果是f应用于该绑定的参数的结果.

好吧,这句话很明显是泥巴,但这非常重要.让我们暂时看看lambda内部.查看函数(>>=)创建的结果,您会看到let {something to do with x} in {something to do with f and the results of the let binding}.这对于懒惰评估很重要.这意味着,仅仅是也许它可以忽略x,也许它的一部分,当判断(>>=),如果特定的功能,f允许它.在惰性的情况下State,这意味着它可能能够延迟计算未来的状态值,如果f可以在查看状态之前生成构造函数.

事实证明这是允许它工作的原因.特殊的方式replicateM组装调用(>>=),它会产生一个函数,(:)在检查传递给它们的状态之前产生构造函数.如果从未检查过最终状态,则允许对列表进行增量处理.如果您查看最终状态,则会破坏逐步运行的能力,因为最终状态需要完成所有工作来计算它.但是你的使用evalState导致最终状态被剔除未经审查,因此评估可以自由地逐步进行.