seq功能和严格性 [英] the seq function and strictness

问题描述

当使用 seq时，我一直很想知道这件事，但我一直无法找到任何有关它的信息。 函数，它是如何真正 的工作？在任何地方，只是解释说 seq ab 会评估 a ，放弃结果并返回 b 。

但那真的 是什么意思？请问以下结果是严格的评估：

pre $ code $ f $ st = seq q（bar qt）其中
q = s * t

我的意思是， q 严格在用于 bar 之前进行评估？以下是相同的：

  foo st = seq（s * t）（bar（s * t）t）
  

我发现要详细了解这个函数的功能有点难。

解决方案

你并不孤单。由于几个不同的原因， seq 可能是最难以使用的Haskell函数之一。在你的第一个例子中：

  foo st = seq q（bar qt）其中
q = s * t 
  

q 在 bar之前评估评估qt 。如果 bar q t 永远不会被评估，那么 q 也不会。所以如果你有

$ pre $ code $ main $
$ val $ foo 10 20
return（）

作为 val 永远不会被使用，它不会被评估。因此 q 也不会被评估。如果您改为

  main = print（foo 10 20）
  

对 foo 10 20 的结果进行评估（通过 print bar foo q c $ c>。

这也是为什么这不起作用：

  myseq x = seq xx 
  

语义上，这意味着第一个在评估第二个 x 之前，将评估x 。但是，如果第二个 x 从未被评估过，那么第一个不需要。所以 seq xx 完全等于 x 。

你的第二个例子可能是也可能不是一回事。这里，在 bar 的输出之前评估表达式 s * t ，但它可能不是相同的 s * t 作为 bar 的第一个参数。如果编译器执行常见的子表达式消除，它可能会共同使用两个相同的表达式。尽管GHC在CSE的哪个位置可以保持相当保守，所以你不能依赖这个。如果我定义 bar qt = q * t ，它会在执行CSE并在使用该值之前评估 s * t 酒吧。对于更复杂的表达式，它可能不会这样做。

您可能还想知道严格评估的含义。 seq 将第一个参数计算为弱头标准形式（WHNF），对于数据类型来说，这意味着解包最外层的构造函数。考虑这个：

pre $ $ $ $ $
$ b $ x $ y $ se $ xs因为 map

xs code>。当 seq 对其进行评估时，它将本质上将代码转换为



  case 
 []的xs  - > map（* y）xs 
（_：_） - > map（* y）xs 
  

这意味着它将确定列表是否为空，然后返回第二个参数。请注意，没有列表值被评估。所以你可以这样做：

  Prelude> seq [未定义] 4 
 4 
  

但不是这个

  Prelude> seq undefined 5 
 ***例外：Prelude.undefined 
  

无论您使用哪种数据类型 seq 的第一个参数，对WHNF的评估将足够远以找出构造函数，而不再进一步。除非数据类型的组件使用爆炸模式标记为严格。然后所有严格的领域也将被评估为WHNF。

(感谢Daniel Wagner在评论中的建议）

对于函数， seq 将评估表达式，直到函数具有lambda显示，这意味着它已准备好应用程序。这里有一些例子可以证明这意味着什么：

   -  ok，lambda是最外层的
 Prelude> seq（\ x  - > undefined）'a'
'a'
 
  - 不行。由于内部seq，`undefined`必须在
之前被评估 -  lambda显示
 Prelude> seq（seq undefined（\ x  - > x））'b'
 ***例外：Prelude.undefined 
  

如果您将lambda绑定视为（内置）数据构造函数，函数中的 seq 与使用数据完全一致。

另外，lambda绑定包含所有类型的函数定义，无论是由lambda表示法还是作为普通函数定义。

HaskellWiki的seq页面的 Controversy 部分对 seq 关于函数。

I have been wondering about this a lot, but I haven't been able to find anything about it.

When using the seq function, how does it then really work? Everywhere, it is just explained saying that seq a b evaluates a, discards the result and returns b.

But what does that really mean? Would the following result in strict evaluation:

foo s t = seq q (bar q t) where
      q = s*t

What I mean is, is q strictly evaluated before being used in bar? And would the following be equivalent:

foo s t = seq (s*t) (bar (s*t) t)

I find it a little hard getting specifics on the functionality of this function.

解决方案

You're not alone. seq is probably one of the most difficult Haskell functions to use properly, for a few different reasons. In your first example:

foo s t = seq q (bar q t) where
      q = s*t

q is evaluated before bar q t is evaluated. If bar q t is never evaluated, q won't be either. So if you have

main = do
    let val = foo 10 20
    return ()

as val is never used, it won't be evaluated. So q won't be evaluated either. If you instead have

main = print (foo 10 20)

the result of foo 10 20 is evaluated (by print), so within foo q is evaluated before the result of bar.

This is also why this doesn't work:

myseq x = seq x x

Semantically, this means the first x will be evaluated before the second x is evaluated. But if the second x is never evaluated, the first one doesn't need to be either. So seq x x is exactly equivalent to x.

Your second example may or may not be the same thing. Here, the expression s*t will be evaluated before bar's output, but it may not be the same s*t as the first parameter to bar. If the compiler performs common sub-expression elimination, it may common-up the two identical expressions. GHC can be fairly conservative about where it does CSE though, so you can't rely on this. If I define bar q t = q*t it does perform the CSE and evaluate s*t before using that value in bar. It may not do so for more complex expressions.

You might also want to know what is meant by strict evaluation. seq evaluates the first argument to weak head normal form (WHNF), which for data types means unpacking the outermost constructor. Consider this:

baz xs y = seq xs (map (*y) xs)

xs must be a list, because of map. When seq evaluates it, it will essentially transform the code into

case xs of
  [] -> map (*y) xs
  (_:_) -> map (*y) xs

This means it will determine if the list is empty or not, then return the second argument. Note that none of the list values are evaluated. So you can do this:

Prelude> seq [undefined] 4
4

but not this

Prelude> seq undefined 5
*** Exception: Prelude.undefined

Whatever data type you use for seqs first argument, evaluating to WHNF will go far enough to figure out the constructor and no further. Unless the data type has components that are marked as strict with a bang pattern. Then all the strict fields will also be evaluated to WHNF.

Edit: (thanks to Daniel Wagner for suggestion in comments)

For functions, seq will evaluate the expression until the function "has a lambda showing", which means that it's ready for application. Here are some examples that might demonstrate what this means:

-- ok, lambda is outermost
Prelude> seq (\x -> undefined) 'a'
'a'

-- not ok.  Because of the inner seq, `undefined` must be evaluated before
-- the lambda is showing
Prelude> seq (seq undefined (\x -> x)) 'b'
*** Exception: Prelude.undefined

If you think of a lambda binding as a (built-in) data constructor, seq on functions is perfectly consistent with using it on data.

Also, "lambda binding" subsumes all types of function definitions, whether defined by lambda notation or as a normal function.

The Controversy section of the HaskellWiki's seq page has a little about some of the consequences of seq in relation to functions.

这篇关于seq功能和严格性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！