haskell - 弱头范式和评估顺序

Question

我读过很多关于弱头范式和序列的文章。但我仍然无法想象 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 的第一个参数？

Answer 1

• The first argument of seq is not guaranteed to be evaluated before the second argument

  不能保证，但编译器会尝试并且通常会在阻止 thunk 构建的情况下执行此操作。这种方法不太有效的情况是并行性，因此需要 pseq – 但对于 foldl' 来说，这不相关。

• The first argument of seq will only be evaluated to weak head normal form

  是的，但是对于内置数字类型 WHNF = NF。

• The evaluation of the first argument of seq will only happen when the second is evaluated to WHNF

  确实如此，这常常会引起困惑。但是 in 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 WHNF

  准确地说，这就是强制 seq 的原因，因为要计算 foldl' (+) 0 (1:xs) 的结果，您需要 foldl' (+) a' xs 为 WHNF，seq 确保在 a' 为 WHNF 之前不会发生这种情况。