-- 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)


-- Computes the n-th Fibonacci number. Complexity: O(n)
fib2 :: Int -> Int
fib2 n = fib2' 0 1 n
 where
  -- Accumulator to compute the next Fibonacci number:
  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)
fib3 :: Int -> Int
fib3 n =
 let -- Accumulator to compute the next Fibonacci number:
     fib3' fibn fibnplus1 n = if n == 0
                                then fibn
                                else fib3' fibnplus1 (fibn + fibnplus1) (n - 1)
 in fib3' 0 1 n

f :: Int -> Int -> Int
-- f x y = y * (1 - y) + (1 + x * y) * (1 - y) + x * y
f x y = let a = 1 - y  
            b = x * y
        in y * a + (1 + b) * a + b
-- f x y = let { a = 1 - y ; b = x * y } in y * a + (1 + b) * a + b

-- Checks whether a number is prime.
isPrim :: Int -> Bool
isPrim n = n /= 1 && notDivides (div n 2)
 where
  notDivides m = m == 1 || mod n m /= 0 && notDivides (m - 1)