fibonacci.hs

-- Tail-recursive Fibonacci

fib n = go n (0, 1)
    where 
  -- (x, y) are the last two calculated Fibonacci numbers
  -- n is how many more Fibonacci steps to take
  -- calling `go` is the final step in evaluating `go (n - 1) (y, x + y)`
  go n (x, _) | n < 1 = x
  go n (x, y)         = go (n - 1) (y, x + y)

-- Naive implementation
-- Note that the second line can be written
-- fib' n = (+) (fib' (n - 1)) (fib' (n - 2))
-- 
-- not tail-recursive since the results of calling fib'
-- are needed before doing (+)
fib' n | n < 1 = 0
fib' n         = fib' (n - 1) + fib' (n - 2)