问题 Haskell - 严格与非严格与foldl

我有一个关于严格与非严格定义的问题。 Haskell wiki-laziness（http://en.wikibooks.org/wiki/Haskell/Laziness）在“黑盒严格性分析”一节中做出如下断言：

[假设函数f采用单个参数。]函数f是严格函数，当且仅当f未定义导致打印错误并停止我们的程序时。

维基对比 const 同 id，分别显示非严格和严格的功能。

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

然而，上述测试似乎断言foldl和foldl'都是严格的。如果它们的任何参数未定义，那么两个函数都会生成undefined：

> 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

有人可以解释一下我错过了什么吗？

谢谢！

9754

2017-11-23 17:34

起源

答案:

更好的定义是：如果在未定义此参数的情况下未定义函数，则该函数在参数中被认为是严格的。

我们来看看foldl的以下定义：

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

由此可以推断出以下内容：

它并不严格 f因为 f在第一个等式中，s值并不重要。
它并不严格 s 或者，因为列表可能是非空的 f 在它的第一个论点中可能是非严格的（想想 flip const）。
但是，在列表参数中是严格的，因为无论如何 f和 s 是的，这个论点必须被评估为所谓的 弱头正常形态。如果可以告诉最外层的构造函数，则代数数据类型的值在WHNF中。换句话说，foldl无法避免查看list参数是否为空列表。因此，至少到目前为止它必须评估列表值。但是，如果该值未定义，则2个方程中没有一个适用，因此应用此方法 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。

2017-11-23 18:38

你引用的wiki部分假设你正在处理一个带有单个参数的函数。与...的情况 foldl 是不同的，首先是因为它采用了多个参数，但更重要的是因为其中一个参数是一个函数。让我们看一些例子，看看具体时间 foldl 它的论点是严格的。（注意以下内容也适用于 foldl'。）

> foldl undefined 0 []
0
> foldl undefined 0 [1]
*** Exception: Prelude.undefined

对于空列表， foldl 不需要传递给它的组合函数。在这种情况下，它在第一个参数中并不严格。

> foldl (+) undefined [1, 2, 3]
*** Exception: Prelude.undefined
> foldl (+) 0 undefined
*** Exception: Prelude.undefined

当你进入时 (+) 作为组合功能，它在起始值和列表中是严格的。这是另一个例子，具有不同的组合功能：

> foldl (flip (:)) undefined [1, 2, 3]
[3,2,1*** Exception: Prelude.undefined

有趣。起始值未定义但似乎调用了 foldl 在抛出异常之前产生了一些结果。那这个呢：

> let (x:xs) = foldl (flip (:)) undefined [1, 2, 3]
> x
3

没有例外。所以我们可以得到一个局部结果出来了 foldl 没有击中可怕的 Prelude.undefined。为什么？

嗯，唯一改变的是我们传递给的组合功能 foldl。而 (+) 有类型（粗略） Int -> Int -> Int， flip (:) 有类型 [a] -> a -> [a]。而 3 + ((2 + 1) + undefined) 不在弱头正常形态并且必须减少使得 undefined 被评估， (3:(2:(1:undefined))) 是弱头正常形式，不需要进一步评估，特别是不需要评估 undefined。

2017-11-23 18:06

值得一提的是，在所有这些例子中， foldl' 和 foldl 表现完全相同。 - Daniel Fischer

答案: