参数传递顺序如何影响 Haskell 中的惰性求值？

Question

我一直在尝试理解 Haskell 中的惰性求值，我基本上将其理解为仅在必须时求值。但是在尝试有效地实施斐波那契时，我遇到了这种（奇怪的？）行为：此实现：

--wrapper function used by both implementations
fib :: Int -> Int
fib x = if x < 0 then 0 else fib2 0 1 x

fib2 :: Int -> Int -> Int -> Int
fib2 x y 0 = x
fib2 x y z = fib2 y (x + y) (z - 1)

即使使用

调用也能正常工作

fib 20000000
> -70318061090422843

在递归调用中交换传递的参数时：

fib2 :: Int -> Int -> Int -> Int
fib2 x y 0 = x
fib2 x y z = fib2 (x + y) x (z - 1)

结果：

fib 20000000
>*** Exception: stack overflow

为什么我不必在第一个示例中告诉编译器急切求值？为什么第二个例子不起作用而第一个例子起作用？

为此，我在 Windows 10 上使用了 GHCi 8.0.1。

Answer 1

首先，请注意您的两个版本之间的差异是定量的，而不是定性的。第一个将在 40000000 的输入上发生堆栈溢出，第二个将在 10000000 的输入上成功完成。看起来第二个版本使用的堆栈是第一个版本的两倍。

基本上，原因是，如果我们为 x 和 y 参数中的 thunk 引入符号 {n}，您的第一个版本会

fib2 {n} {n+1} 0 = {n}
fib2 {n} {n+1} z = let {n+2} = (+) {n} {n+1}    -- build a thunk
                    in fib2 {n+1} {n+2} (z - 1)

而第二个版本

fib2 {n+1} {n} 0 = {n+1}
fib2 {n+1} {n} z = let {n+2} = (+) {n+1} {n}    -- build a thunk
                    in fib2 {n+2} {n+1} (z - 1)

现在考虑当 fib2 递归结束时会发生什么，是时候计算 {n}（或 {n+1}；让我们忽略这个差异）。每个 thunk {0}, ..., {n} 将按某种顺序只计算一次。碰巧 (+) 先计算它的左参数，然后再计算它的右参数。为了明确起见，我们只取 n = 6。评价好像

{6} = (+) {4} {5}
... {4} = (+) {2} {3}
... ... {2} = (+) {0} {1}
... ... ... {0} = 0
... ... ... {1} = 1
... ... {2} = 1
... ... {3} = (+) {1} {2}
... ... ... {1} = 1
... ... ... {2} = 1   -- we already calculated it
... ... {3} = 2
... {4} = 3
... {5} = ......

堆栈永远不会超过 n/2 层，因为我们首先从 {n} 递归到 {n-2} 并且当我们需要计算 {n-1} 时我们已经计算了{n-2}.

相比之下，在第二个版本中，我们首先从 {n} 递归到 {n-1}，因此堆栈将具有 n 层。

参数传递顺序如何影响 Haskell 中的惰性求值？

How does argument passing order affect lazy evaluation in Haskell?

recursion

haskell

lazy-evaluation