module Fibonacci where
    -- Classic imperative Fibonacci
    -- XXX: This seems to give odd answers! "fib_simple 0" gives 1 when it should be 0 (0-based indexing) or an error (1-based indexing)!
    fib_simple :: Integer -> Integer
    fib_simple 0 = 1
    fib_simple 1 = 1
    fib_simple x = fib_simple (x - 1) + fib_simple (x - 2)

    -- Fibonacci with tuples and effective caching
    -- This works by using the parameter as the number of steps and iterating those in the tuple
    -- Note: We're zero-indexing, so "fib 0" is the first Fibonacci number
    fib :: Integer -> Integer
    fib x = fibResult (fibTuple (0, 1, x))

    fibResult :: (Integer, Integer, Integer) -> Integer
    fibResult (x, y, z) = x

    fibTuple :: (Integer, Integer, Integer) -> (Integer, Integer, Integer)
    fibTuple (x, y, 0) = (x, y, 0)
    fibTuple (x, y, index) = fibTuple (y, x + y, index -1)