Как Haskell оценивает функцию Фибоначчи?

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).

Другой способ взглянуть на это заключается в следующем. Все определение 3-линии может быть эквивалентно выражено с использованием case как

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