Haskell. Хвостовая рекурсия и фибоначчи

Решаю задачу с рядом фибоначчи (+ отрицательные). Приблизительно так:
fibonacci 0 = 0 fibonacci 1 = 1 fibonacci n | n == 0 = 1 | n > 0 = fibonacci (n - 1) + fibonacci (n - 2) | n < 0 = fibonacci (n + 2) - fibonacci (n + 1)
нужно увеличить скорость просчета. для этого естественно нужен аккумулятор.
Как это сделать?

Ответ

Правильнее всего, конечно, использовать готовую формулу n-ого члена :) Но для случая, когда нужно находить программным путём, подходит следующая идея (пишу алгоритм, не знаю синтаксис Хаскеля):
fib n = helper 0 1 n where helper curr prev n | n == 0 = curr | n > 0 = helper (curr+prev) curr (n-1) | n < 0 = helper prev (curr-prev) (n+1)
Это вычисляет последовательность за линейное время с хвостовой рекурсией.