参数传递顺序如何影响Haskell中的延迟评估？

我一直试图理解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.

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

基本上,原因是,如果我们引入{n}生活在x和y参数中的thunk 的符号,你的第一个版本确实如此

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}让我们忽略这种差异).每个thunks {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水平.