弱首标的形式和评价顺序

问题描述

我读了很多关于弱头正常形式和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 的第一个参数？

解决方案

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

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


  正是这导致 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?

解决方案

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

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

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

  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.

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