-- Computes the factorial of a number
fac :: Integer -> Integer
fac n = if n == 0 then 1 else n * fac (n - 1)

-- Special case: fac 0 = if 0 == 0 then 1 else 0 * fac (0 - 1)

{-
Computation: replacing equals by equals

fac 2 = if 2 == 0 then 1 else 2 * fac (2 - 1)
      = if False  then 1 else 2 * fac (2 - 1)
      = 2 * fac (2 - 1)
      = 2 * fac 1
      = 2 * (if 1 == 0 then 1 else 1 * fac (1 - 1))
      = 2 * (if False  then 1 else 1 * fac (1 - 1))
      = 2 * (1 * fac (1 - 1))
      = 2 * (1 * fac 0)
      = 2 * (1 * (if 0 == 0 then 1 else 0 * fac (0 - 1)))
      = 2 * (1 * (if True   then 1 else 0 * fac (0 - 1)))
      = 2 * (1 * 1)
      = 2
-}

-- Fibonacci number (clear and precise definition):
fib1 :: Int -> Int
fib1 n = if n == 0
           then 0
           else if n == 1
                  then 1
                  else fib1 (n-1) + fib1 (n-2)


-- Fibonacci number by iteration:
fib2iter :: Int -> Int -> Int -> Int
fib2iter fibn fibnp1 n = if n == 0 then fibn
                                   else fib2iter fibnp1 (fibn + fibnp1) (n - 1)

fib2 :: Int -> Int
fib2 n = fib2iter 0 1 n

{-
fib2 5 = fib2iter 0 1 5
   ... = fib2iter 1 1 4
   ... = fib2iter 1 2 3
   ... = fib2iter 2 3 2
   ... = fib2iter 3 5 1
   ... = fib2iter 5 8 0
   ... = 5
-}


-- Fibonacci number by iteration:
fib3 :: Int -> Int
fib3 n = fib3iter 0 1 n
 where 
  fib3iter fibn fibnp1 n = if n == 0 then fibn
                                     else fib3iter fibnp1 (fibn + fibnp1) (n - 1)


-- Fibonacci number by iteration:
fib4 :: Int -> Int
fib4 n =
 let fib4iter fibn fibnp1 n = if n == 0
                                then fibn
                                else fib4iter fibnp1 (fibn + fibnp1) (n - 1)
 in fib4iter 0 1 n

-- let expression to structure expressions:
f x y = y * (1 -y) + (1 + x * y) + (1 - y) * x * y

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


---------------------------------------------

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