haskell - 参数传递顺序如何影响 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 的输入上成功完成.看起来第二个版本使用的堆栈是第一个版本的两倍。

基本上，原因是，如果我们引入符号 {n}对于生活在 x 中的 thunk和 y论点，你的第一个版本确实

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水平。