我读过很多关于弱头范式和序列的文章。但我仍然无法想象 Haskell 求值顺序背后的逻辑
一个常见的例子演示了何时以及如何使用,但我仍然不明白常见的例子是如何使用的
foldl (+) 0 [1..5000000]
可能导致堆栈溢出。而使用 seq
的另一个折叠定义则不然
foldl' _ a [] = a
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
foldl' (+) 0 [0..5000000]
从我读过的 seq 解释来看,作者非常小心地阐明了以下内容:
- 不保证
seq
的第一个参数在第二个参数之前计算 seq
的第一个参数只会被评估为弱头范式- 仅当第二个参数计算为 WHNF 时,才会计算
seq
的第一个参数
那么,如果上面是正确的(是吗?)那么为什么 foldl'
不会像 foldl
那样溢出?
当我们减少一步时,不应该是这样的吗?
foldl' (+) 0 (1:xs) = let a' = (+) 0 1 in a' `seq` foldl' (+) a' xs
在上面,seq
的第二个参数不在WHNF中,因为有一个函数应用需要完成。我们是否保证在到达第二个参数的 WHNF 之前先计算 seq
的第一个参数?
最佳答案
-
The first argument of
不能保证,但编译器会尝试并且通常会在阻止 thunk 构建的情况下执行此操作。这种方法不太有效的情况是并行性,因此需要seq
is not guaranteed to be evaluated before the second argumentpseq
– 但对于foldl'
来说,这不相关。 -
The first argument of
是的,但是对于内置数字类型 WHNF = NF。seq
will only be evaluated to weak head normal form -
The evaluation of the first argument of
确实如此,这常常会引起困惑。但是seq
will only happen when the second is evaluated to WHNFin a' `seq` Foldl' f a' xs
意味着,如果您请求任何结果,它将触发seq
。When we reduce one step, shouldn't it looks like this, right? ... the second argument of
准确地说,这就是强制seq
is not in WHNFseq
的原因,因为要计算foldl' (+) 0 (1:xs)
的结果,您需要foldl' (+) a' xs
为 WHNF,seq
确保在a'
为 WHNF 之前不会发生这种情况。
关于haskell - 弱头范式和评估顺序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23313291/