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

В настоящее время я смотрю на эту функцию в 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 возвращает результат. Так что я делаю неправильно?


recursion haskell reduction fibonacci
person user2426316    schedule 15.03.2015    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Порядок уравнений в определении имеет значение.

Часть

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)
person chi    schedule 15.03.2015
comment
спасибо, часть gets applied only when the previous lines do not apply прояснила мне - person user2426316; 15.03.2015