14

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

[假设函数 f 接受单个参数。] 函数 f 是严格函数当且仅当 f undefined 导致打印错误并停止我们的程序。

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

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

谢谢！

4

2 回答 2

11

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

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

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

由此可以得出以下结论：

  1. 它在 中并不严格f，因为fs 值在第一个方程中并不重要。
  2. 两者都不严格s，因为列表可能是非空的，并且f在它的第一个参数中可能是非严格的（想想flip const）。
  3. 然而，它在 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, where...代表左侧必须首先评估左侧，依此类推，从上到下f s x_1。

因此我们有它

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

是n，而

foldl const 0 [1..n]

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

于 2012-11-23T18:38:04.490 回答
4

您引用的 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不会碰到 dreadd Prelude.undefined。为什么？

好吧，唯一改变的是我们传递给的组合函数foldl。而(+)有类型（大致）Int -> Int -> Int，flip (:)有类型[a] -> a -> [a]。而3 + ((2 + 1) + undefined)不是弱头范式，必须减少，以便undefined评估 ，(3:(2:(1:undefined))) 是弱头范式，不需要进一步评估，特别是不需要评估undefined.

于 2012-11-23T18:06:54.663 回答