-- Haskell fibonacci functions.
-- 0  1  2  3  4  5   6   7 ... (index)
-- 1  1  2  3  5  8  13  21 ... (value)
-- Each value (after the first two) is the sum of the two previous.

-- A.  naive

-- Integers can be larger than Ints
nfib :: Integer -> Integer

nfib 0 = 1
nfib 1 = 1
nfib n = nfib (n - 1) + nfib (n - 2)

-- fast, still recursive

ffib :: Integer -> Integer

ffib n = 
    if n < 2
    then 1
    else fibloop 1 1 2 n

-- fibloop a b i n computes the nth fibonacci number, fib n,
-- given that a and b are the immediate predecessors of fib i,
-- that is, a is fib (i - 2) and b is fib (i - 1).

fibloop a b i n =
    let c = b + a -- = fib i
    in if i == n
       then c
       else fibloop b c (i + 1) n