Haskell - 使用foldl时的严格和非严格区别

Question

我有一个关于 strict 和 non-strict 定义的问题。Haskell 惰性计算的维基书（http://en.wikibooks.org/wiki/Haskell/Laziness）在“黑盒严格性分析”一节中作出以下断言：

 

[假设有一个只有一个参数的函数 f。] 当且仅当 f undefined 导致错误被打印并停止程序时，函数 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

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

谢谢！

- shj

Answer 1

更好的定义是：如果一个函数在某个参数上未定义，那么这个函数被称为在该参数上严格。

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

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

由此可以得出以下结论：

1. f不是严格的，因为在第一个方程中f的值是无关紧要的。
2. s也不是严格的，因为列表可能是非空的，而f在其第一个参数上可能是非严格的（考虑flip const）。
3. 然而，在列表参数中是严格的，因为无论f和s是什么，都必须计算这个参数到所谓的弱头正常形式。代数数据类型的值在WHNF中，如果你能告诉最外层的构造函数。换句话说，foldl没有办法避免查看列表参数是否为空列表。因此，它必须至少评估列表值到某种程度。但如果该值未定义，则两个方程都不适用，因此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]

foldl const 0 [1..n]

当n足够大时，程序将会出现堆栈溢出。这是人类在计算方面比机器更擅长的明确标志，因为在第二个例子中，列表的长度和内容都是无关紧要的，大多数人都能立即看出结果必须为0。

- Ingo

Answer 2

你引用的维基百科部分假设你正在处理只带有一个参数的函数。而 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。

- seliopou

---

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