{-  Recursive Function Examples
    Chapter 3, Evaluation and Efficiency
    Introduction to Functional Progamming Using Haskell
    H. Conrad Cunningham

1234567890123456789012345678901234567890123456789012345678901234567890

2016-07-27: Module based on previous work
2017-09-95: Revised for CSci 450/503 version of Chapter 3

-}

module EvalEff
    ( fact1, fact4, fact5, fact6, fib, fib2, expt, expt2, expt3 )
where

fact1 :: Int -> Int 
fact1 n = if n == 0 then 
              1
          else
              n * fact1 (n-1)

fact4 :: Int -> Int 
fact4 n 
  | n == 0 =  1 
  | n >= 1 =  n * fact4 (n-1)

fact5 :: Int -> Int  
fact5 n = product [1..n]

fact6 :: Int -> Int 
fact6 n = factIter n 1 

-- not exported
factIter :: Int -> Int -> Int 
factIter 0 r         = r 
factIter n r | n > 0 = factIter (n-1) (n*r) 
  
fib :: Int -> Int
fib 0          = 0
fib 1          = 1 
fib n | n >= 2 = fib (n-1) + fib (n-2)

fib2 :: Int -> Int
fib2 n = fibIter n 0 1
    where
        fibIter :: Int -> Int -> Int -> Int
        fibIter 0 p q         = p
        fibIter n p q | n > 0 = fibIter (n-1) q (p+q)

expt :: Integer -> Integer -> Integer
expt b 0        = 1
expt b n 
    | n > 0     = b * expt b (n-1)  -- backward recursive
    | otherwise = error ("expt not defined for negative exponent " 
                         ++ show n)

expt2 :: Integer -> Integer -> Integer
expt2 b n | n < 0 = error ("expt2 not defined for negative exponent " 
                           ++ show n)
expt2 b n         = exptIter n 1
    where exptIter 0 p = p  
          exptIter m p = exptIter (m-1) (b*p) -- tail recursive

expt3 :: Integer -> Integer -> Integer
expt3 _ n | n < 0 = error ("expt3 not defined for negative exponent"
                           ++ show n)
expt3 b n         = exptAux n
    where exptAux 0 = 1
          exptAux n
            | even n    = let exp = exptAux (n `div` 2) in 
                              exp * exp      -- backward recursive
            | otherwise = b * exptAux (n-1)  -- backward recursive
 
-- Exercise:  Can you implement a tail recursive version of expt3?

-- Testing of expt

bases  = [2,3,6]
powers = [0,1,2,3,4,5,6,7,8,9,10,20]

result_expt = [ expt b n | b <- bases, n <- powers ]

-- Testing of expt2

result_expt2 = [ expt2 b n | b <- bases, n <- powers ]

-- Testing of expt3

result_expt3 = [ expt3 b n | b <- bases, n <- powers ]