Haskell如何评估Fibonacci函数？

Question

我目前正在Haskell中查看这个函数，它在n位置返回斐波纳契数。

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

现在，它编译，返回正确的结果和一切..。但我不明白Haskell是如何评估这个函数的。

Haskell不是一直在寻找一个合适的定义，然后再应用这个定义直到它不能再使用(例如，达到基本情况)吗？

在这种情况下，这就是我想出来的。例如，评估fib 3

fib n = fib (n-1) + fib (n-2)
fib 3 = fib (3-1) + fib (3-2)
fib 3 = fib ((3-1)-1) + fib ((3-1)-2) + fib ((3-2)-1) + fib ((3-2)-2)
fib 3 = fib (((3-1)-1)-1) + fib (((3-1)-1)-2) +
        fib (((3-1)-2)-1) + fib (((3-1)-2)-2) + 
        fib (((3-2)-1)-1) + fib (((3-2)-1)-2) + 
        fib (((3-2)-2)-1) + fib (((3-2)-2)-2)
...

这可能会永远持续下去，而不会给出实际的结果。但是，Haskell返回一个结果。那我做错什么了？

Answer 1

定义中方程的顺序确实很重要。

部分

fib n = fib (n-1) + fib (n-2)

仅当前面的行不应用时才应用。也就是说，只有当n既不是0也不是1的时候。因为这个，这个步骤

fib 3 = fib (3-1) + fib (3-2)
fib 3 = fib ((3-1)-1) + fib ((3-1)-2) + fib ((3-2)-1) + fib ((3-2)-2)

错了：fib (3-2)是fib 1 = 1，而不是fib ((3-2)-1) + fib ((3-2)-2)。

另一种看待is的方法如下所示。整个3行定义可以用case表示为

fib n = case n of
        0 -> 0
        1 -> 1
        m -> fib (m-1) + fib (m-2)