-- 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 with accumulator: complexity O(n)
fib2 :: Int -> Int
fib2 n = fib2iter 0 1 n
 where
  -- Iterative version with accumulator
  fib2iter :: Int -> Int -> Int -> Int
  fib2iter fibn fibnp1 n = if n == 0
                             then fibn
                             else fib2iter fibnp1 (fibn + fibnp1) (n - 1)

fib2let :: Int -> Int
fib2let n =
 let fib2iter fibn fibnp1 n = if n == 0
                                then fibn
                                else fib2iter fibnp1 (fibn + fibnp1) (n - 1)
 in fib2iter 0 1 n


letexp1 = 3 + (let y = 40 - 1
               in y * 4)

letexp2 = (let x = 40
               y = 1
           in x + y) * 2

letexp3 = (let { x = 40 ; y = 1 } in x + y) * 2

letexp4 = (let
            x = 40
            y = 1
           in x + y) * 2

f x y = y * (1 - y) + (1 + x * y) * (1 - y) + (x * y)

g x y = let a = 1 -y
            b = x * y
        in y * a + (1 + b) * a + b

-- Is a number a prime number?
isPrim :: Int -> Bool
isPrim n = n /= 1 && noSmallerDiv (div n 2)
 where
  noSmallerDiv t = t == 1 || (mod n t /= 0 && noSmallerDiv (t - 1))