-- Use the SimpleHaskell prelude
import SimplePrelude

-- Computes the square of a number.
square :: Int -> Int
square n = n * n

-- Computes the minimum of two numbers:
mini :: Int -> Int -> Int
mini x y = if x < y then x else y

-- Computes the factorial function.
fac :: Int -> Int
fac n = if n == 0 then 1 else n * fac (n - 1)


-- Computes the n-th Fibonacci number. Complexity: O(2^n)
fib1 :: Int -> Int
fib1 n = if n == 0
           then 0
           else if n == 1
                  then 1
                  else fib1 (n - 1) + fib1 (n - 2)

-- Accumulator to compute the next Fibonacci number:
fib2' :: Int -> Int -> Int -> Int
fib2' fibn fibnplus1 n = if n == 0
                           then fibn
                           else fib2' fibnplus1 (fibn + fibnplus1) (n - 1)

-- Computes the n-th Fibonacci number. Complexity: O(n)
fib2 :: Int -> Int
fib2 n = fib2' 0 1 n