理解惰性求值

Question

我正在尝试理解Haskell中惰性求值的内部运作机制。

如果我有这样一个函数调用：

negate $ 5 * sqrt 16

我的理解是Haskell会首先处理sqrt 16，创建一个thunk并在需要时计算其值。

但是，当sqrt 16传递给乘法时，它是否被评估，还是只有在以某种方式输出到控制台时才被评估？

换句话说，当输入到GHCi（例如）时，表达式的每个部分将按什么顺序进行评估？

- Tom Savage

---

你读过维基百科上的内容了吗？http://www.haskell.org/haskellwiki/Performance/Laziness - Devin M

谢谢提供链接。里面的信息非常有帮助。 - Tom Savage

由DonS提供了许多参考资料，而且帖子的楼主也很有帮助：http://www.reddit.com/r/programming/comments/i4jb1/haskells_evaluation_isnt_magic/c21369j - Gene T

Answer 1

默认情况下，每个函数和构造器调用都成为thunk。因此，在这种情况下，评估过程如下：

evaluate "negate $ 5 * sqrt 16" -> <thunk> $ <thunk>
 evaluate "negate"               -> <func>
 evaluate "5 * sqrt 16"          -> <thunk> * <thunk>
  evaluate "5"                    -> 5.0
  evaluate "sqrt 16"              -> 4.0

<thunk> 意味着某些东西是一个thunk，而 <func> 意味着它是一个函数值，无法表示为字符串。

缩进意味着“父级”将在评估自身之前评估“子级”。

因此，如果您编写 print (negate $ 5 * sqrt 16)，运行时将执行以下步骤：

eval thunk:
  <thunk 1> $ <thunk 2>
eval thunk 1:
  <func> $ <thunk 2>
eval thunk 2:
  <func> $ <thunk 3> * <thunk 4>
(cheating a little here, because (*) is strict, so these three are actually
 one step:)
eval thunk 3:
  <func> $ 5 * <thunk 4>
eval thunk 4 by applying sqrt:
  <func> $ 5 * 4
apply (*):
  <func> $ 20
apply ($):
  -20

- dflemstr

Answer 2

你可以将其视为从外到内的过程，即首先调用negate。然后它将强制执行其参数，这可能会强制执行其他表达式的评估等等。你可以使用Debug.Trace.trace进行实验，它在计算时打印第一个参数并返回第二个参数，以便准确查看GHCi中发生的顺序：

> trace "A" (negate (trace "B" (5 * (trace "C" (sqrt 16)))))
A
B
C
-20.0

然而，需要注意的是编译器允许执行可能改变表达式计算顺序的优化，这就是为什么在顺序很重要时我们使用 IO monad 的原因。

- hammar

Answer 3

表达式在需要该值时被计算。因此，如果您写入以下内容：

f = negate $ 5 * sqrt 16

只有使用f才会进行评估。 negate需要5 * sqrt 16，而sqrt 16也需要被计算。评估过程一直展开，直到达到基本情况，然后对其进行评估，然后用于先前/更高表达式（现在向后走），直到整个表达式都被评估。

- Emil

Answer 4

首先，创建整个表达式的thunk。由于*是严格的，因此取决于优化（可能使用直接调用sqrt），sqrt 16的thunk可能会或可能不会在其中被创建。然后当它被强制执行（需要其值）时，negate将强制执行其参数，即*表达式，并且作为严格的，*将强制执行其两个参数并产生值20。

顺便说一下，我认为当你谈论Haskell时，应该谈论非严格语义。 "Thunk"和"lazy"属于实现细节。

- Will Ness

Answer 5

我曾在某处阅读到的一种思考方法，对我在这方面很有帮助，即采用以下方式来看待这个问题:

• 每个表达式都会产生一个thunk(延迟计算)。
• 当需要其值时，将强制执行thunk。
• “需要”的概念是您可以称之为“条件强制”:“假设强制执行thunk T, 这会导致哪些其他thunk被强制执行?” 如果强制一个应用该函数的thunk会导致它的参数的thunk被强制执行，则该函数在其参数上是严格的。

因此，通过调用适当的show方法，将值打印到控制台；即，打印到控制台会强制执行形式为show x(对于某个x)的表达式。 强制执行show x会强制执行x。 假设x是negate $ 5*sqrt 16;由于negate在其参数中是严格的，因此强制执行该thunk也会强制执行5*sqrt 16的thunk。 同样，*和sqrt在其参数中也是严格的，因此必须强制执行5，sqrt 16和16的thunk。

另一个需要理解的问题是数据构造函数和模式匹配如何影响延迟计算。基本上，除非有特殊的严格性标注，否则构造函数就像非严格函数一样，即强制执行thunk并不会强制执行构造函数的参数。除非使用了特殊的惰性模式匹配语法，否则匹配构造函数会强制执行参数的thunk。 因此我们有:

identity x = x  -- irrefutable pattern; `x` is not forced

uncons (x:xs) = (x, xs)  -- match against (:) constructor; argument 
                         -- must be forced, but x and xs aren't forced

foo (x:x':xs) = (x, x', xs) -- two matches against (:) constructor;
                            -- the argument thunk is forced, as is its
                            -- tail thunk.

- Luis Casillas

---

“show x” 本身并不强制执行 “x”。只有在强制执行 “show x” 时，它才会强制执行 “x”。 - newacct

我会编辑答案以更清楚地表达这个意思，但在这个上下文中，“show x”被强制执行，因为我们正在将其结果打印到控制台上。而“show x”是否强制执行“x”实际上取决于“x”的类型以及该类型的“show”方法；所以严格来说，我假设像“show（x :: Double）”这样的东西会强制执行“x”。 - Luis Casillas

+1 是强制操作的具体实现。尽管在调用 show 时，值不会被打印到控制台上；经过编辑后，这仍然相当令人困惑，特别是涉及到时间和行动的发起者。一个新手可能会从该句子的前半部分得出结论，他在“调用” show 时打印值。不，系统会执行打印操作，并在此过程中强制相应的 show 调用。 - Will Ness