Haskell - 严格与非严格的foldl [英] Haskell - strict vs non-strict with foldl

问题描述

我有一个关于严格与非严格的定义的问题。 Haskell Laziness的wiki书（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 
  

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

谢谢！

解决方案

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

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

  foldl fs [] = s 
 foldl fs（x：xs）= foldl f（fsx）xs 
  

由此可以得出以下结论：

1. 它在 f 中并不严格，因为 f s的值在第一个中并不重要
   
2. 在 s 中也不是严格的，因为列表可以是非空的， f 在它的第一个参数中可以是非严格的（认为 flip const ）。


3. 列表参数，但是，因为，不管 f 和 s 是，这个参数必须被评估为所谓的弱头标准形式。如果可以告诉最外层的构造函数，那么代数数据类型的值在WHNF中。换言之，foldl无法避免查看列表参数是否为空列表。因此，它至少必须对列表值进行评估。但是如果这个值是未定义的，那么这两个方程都不适用，因此 foldl 的这个应用本身是未定义的。

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

 （（（（s`f 'x'）`f` x_2）`f` x_3）....）`f` x_n）
  

<现在，如果 f 本身在其左参数中是严格的，比如（+），那么任何试图评估需要foldl的结果需要与列表长度成正比的堆栈空间。对于评估 f ... x_n ，其中 ... 代表左手边必须先评估左手边等等，下降到 fs x_1 并返回。

因此我们知道 p>

  foldl（flip const）0 [1..n] 
  

是 n ，而

  foldl const 0 [1..n] 
  

将足够大的ñ。这是一个可靠的指标，在​​这里人类比计算机更擅长计算，因为在第二个例子中，列表的长度和内容是完全不相关的，大多数人会立即看到结果必须为0。

I have a question concerning the definition of strict vs non-strict. The Haskell wiki-book for Laziness (http://en.wikibooks.org/wiki/Haskell/Laziness), under the section "Black-box strictness analysis", makes the following assertion:

[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.

The wiki contrasts const with id, showing a non-strict and strict function respectively.

My question is that I was under the impression that foldl was evaluated in a non-strict fashion, causing undesirable space-leaks, while foldl' was strict.

However, the above test seems to assert that both foldl and foldl' are strict. That is both functions produce undefined if any of their parameters are 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

Could someone please explain what I'm missing?

Thanks!

解决方案

A better definition is: A function is said to be strict in an argument if it is undefined in the case that this argument is undefined.

Let us look at the following definition of foldl:

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

From this the following can be deduced:

1. It is not strict in f, because fs value is immaterial in the first equation.
2. It is not strict in s either, since the list could be non-empty and f could be non-strict in it's first argument (think flip const).
3. It is strict in the list argument, however, because, no matter what fand s are, this argument must be evaluated to so called weak head normal form. A value of algebraic data type is in WHNF if you can tell the outermost constructor. Put differently, there is no way that foldl can avoid looking if the list argument is an empty list or not. And hence, it must evaluate the list value at least so far. But if that value is undefined, none of the 2 equations is applicable, hence this application of foldl is itself undefined.

Furthermore, from the fact that foldl is not strict in the accumulator s we can also learn why it is in many cases a bad idea to use foldl: The system sees no reason to actually evaluate the term f s x, since it is passed to a function that is not strict in the corresponding argument. Indeed, it would be a violation of non-strictness principles if it did evaluate it. Hence, depending on the length of the list, a huge thunk is accumulated in the accumulator:

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

Now, if f itself is strict in its left argument, like (+), any attempt to evaluate the result of foldl with necessity needs stack space proportional to the length of the list. For, evaluation of f ... x_n, where ... stands for the left hand side must first evaluate that left hand side, and so on, down to f s x_1 and back.

Hence we have it that

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

is n, while

foldl const 0 [1..n]

will stack overflow for large enough n. This is a sure indicator that here are cases where humans are better at computing than machines, as in the second example the length and content of the list are completely irrelevant and most people will see immediately that the result must be 0.

这篇关于Haskell - 严格与非严格的foldl的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！