Haskell - 严格与非严格与 foldl

Question

我对严格与非严格的定义有疑问。 Haskell wiki-book for Laziness (http://en.wikibooks.org/wiki/Haskell/Laziness) 在“黑盒严格性分析”部分下做出以下断言:

[Assuming a function f which takes a single parameter.] The function f is a strict function if, and only if, f undefined results in an error being printed and the halting of our program.

wiki 对比 const与 id ，分别表示非严格和严格函数。

我的问题是，我的印象是 foldl 是以非严格的方式评估的，导致不希望的空间泄漏，而 foldl' 是严格的。

然而，上面的测试似乎断言 foldl 和 foldl' 都是严格的。如果它们的任何参数未定义，则这两个函数都会产生未定义:

> Data.List.foldl (+) undefined [1,2,3,4]
    Prelude.undefined
> Data.List.foldl' (+) 0 undefined
    Prelude.undefined
> Data.List.foldl' (+) undefined [1,2,3,4]
    Prelude.undefined
> Data.List.foldl (+) 0 undefined
    Prelude.undefined

有人可以解释我缺少什么吗？

谢谢!

Answer 1

一个更好的定义是:如果一个函数在这个参数未定义的情况下是未定义的，则称该函数在一个参数中是严格的。

让我们看一下 foldl 的以下定义:

 foldl f s [] = s
 foldl f s (x:xs) = foldl f (f s x) xs

由此可以得出以下结论:

f 中不严格, 因为 f s 值在第一个等式中无关紧要。

s 中不严格或者，因为列表可能是非空的并且 f在它的第一个参数中可能是非严格的(想想 flip const )。

然而，在 list 参数中它是严格的，因为无论如何 f和 s是，这个参数必须被评估为所谓的弱头范式。如果您可以告诉最外层的构造函数，则代数数据类型的值在 WHNF 中。换句话说， foldl 无法避免查看 list 参数是否为空列表。因此，它必须至少到目前为止评估列表值。但如果该值未定义，则这两个方程都不适用，因此 foldl 的应用本身是未定义的。

此外，根据 foldl累加器不严格 s我们还可以了解为什么在许多情况下使用 foldl 是个坏主意: 系统认为没有理由实际评估术语 f s x ，因为它被传递给相应参数中不严格的函数。事实上，如果它确实评估它，那将违反非严格性原则。因此，根据列表的长度，在累加器中会累积一个巨大的 thunk:

((((s `f` x_1) `f` x_2) `f` x_3) ....) `f` x_n)

现在，如果 f其左参数本身是严格的，如 (+) ，任何评估 foldl 结果的尝试都需要与列表长度成比例的堆栈空间。对于 f ... x_n 的评估, 其中 ...代表左侧必须首先评估左侧，依此类推，直到 f s x_1然后回来。

因此我们有它

foldl (flip const) 0 [1..n]

是 n ， 尽管

foldl const 0 [1..n]

将堆栈溢出足够大 n .这是一个明确的指标，表明在某些情况下人类比机器更擅长计算，因为在第二个示例中，列表的长度和内容完全不相关，大多数人会立即看到结果必须为 0。