弱首标的形式和评价顺序 [英] Weak head normal form and order of evaluation

问题描述

我读了很多关于弱头正常形式和seq的文章。但我仍然很难想象Haskell评估顺序背后的逻辑。

一个常见示例演示何时以及如何使用，但我仍不明白常见示例

  foldl（+）0 [1..5000000] 
  

会导致堆栈溢出。虽然使用 seq 的另一个折叠定义不包含

  foldl'_ a [] = a 
 foldl'fa（x：xs）= let a'= fax in a``seq` foldl'f a'xs 
 foldl'（+）0 [0..5000000] 
  

从我读过的seq的解释可以看出，作者非常小心地明确以下内容： / p>

• seq 的第一个参数不保证在第二个参数


• seq 的第一个参数只能评估为弱头标准格式


• 评估 seq 的第一个参数只会在第二个参数被计算为WHNF时发生

<那么，为什么 foldl'不会像 foldl 那样溢出？

当我们减少一步时，它不应该是这样吗？ code> foldl'（+）0（1：xs）= let a'=（+）0 1 i （+）a'xs

在上面的第二个参数 seq 不在WHNF中，因为有一个功能应用程序需要完成。在我们到达第二个参数的WHNF之前，我们是否保证在这里评估 seq 的第一个参数？

解决方案

• seq 的第一个参数不保证在第二个参数

  不保证，但编译器会尝试并通常在阻止thunk建立的情况下执行它。这种情况不适用于并行性，因此需要 pseq - 但是对于 foldl'而言并不相关。



• seq 的第一个参数只能评估为弱头标准格式

  是的，但是对于内置的数字类型WHNF = NF。
  

• 对第一个参数 seq 的评估仅在第二个参数评估为WHNF时才会发生

  事实上，这经常会导致混乱。但是在'seq` foldl'f a'xs >中的意味着，如果你请求任何结果，它将触发 seq 。


  当我们减少一步时，它看起来不是这样吗？ ... seq 的第二个参数不在WHNF中

  正是这导致 seq ，因为要评估 foldl'（+）0（1：xs）的结果，您需要 foldl'（+）a 'xs 为WHNF，并且 seq 确保在 a'之前不会发生这种情况。是WHNF。




I've read lots on weak head normal form and seq. But I'm still have trouble imagining the logic behind Haskell's order of evaluation

A common example demonstrating when and how to use but I still don't understand how the common example

foldl (+) 0 [1..5000000]

can result in a stack overflow. While another fold definition using seq doesn't

foldl' _ a [] = a
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
foldl' (+) 0 [0..5000000]

From explanations of seq that I've read, authors are very careful to make the following clear:

• The first argument of seq is not guaranteed to be evaluated before the second argument
• The first argument of seq will only be evaluated to weak head normal form
• The evaluation of the first argument of seq will only happen when the second is evaluated to WHNF

So, if the above is correct (is it?) then why does foldl' not overflow like foldl?

When we reduce one step, shouldn't it looks like this, right?

foldl' (+) 0 (1:xs) = let a' = (+) 0 1 in a' `seq` foldl' (+) a' xs

In the above, the second argument of seq is not in WHNF since there is a function application which needs to be done. Are we guaranteed to evaluate the first argument of seq here before we reach the WHNF of the second argument?

解决方案

• The first argument of seq is not guaranteed to be evaluated before the second argument

  Not guaranteed, but the compiler will try and usually do it if it prevents thunk buildup. The scenario where this doesn't work so well is parallelism, hence the need for pseq – but for foldl' that's not relevant.

• The first argument of seq will only be evaluated to weak head normal form

  Yeah, but for built-in number types WHNF = NF.

• The evaluation of the first argument of seq will only happen when the second is evaluated to WHNF

  Indeed, and that often causes confusion. But in a' `seq` foldl' f a' xs means, if you request any result at all it'll trigger the seq.

  When we reduce one step, shouldn't it looks like this, right? ... the second argument of seq is not in WHNF

  Precisely that's what forces the seq, because to evaluate the result of foldl' (+) 0 (1:xs) you need foldl' (+) a' xs to be WHNF, and seq ensures this won't happen before a' is WHNF.

这篇关于弱首标的形式和评价顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！