{-  Exploring Languages with Interprters and Functional Programming
    Chapter 9 -- Recursion Styles Haskell Examples
    Copyright (C) 2018, H. Conrad Cunningham

1234567890123456789012345678901234567890123456789012345678901234567890

2016-07-27: Module based on previous work
2017-08-25: Revised for 2017 textbook Chapter 3
2018-06-07: Revised for 2018 textbook Chapter 9
2018-07-04: Removed fact4, fact6; see ../Ch04/Factorial.hs;
            Added f, g 
            Added copyright notice

-}


module RecursionStyles
    ( fib, fib2, expt, expt2, expt3, f, g )
where

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

-- Exponentiation functions
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?

-- Local definitions
-- let
f :: [Int] -> [Int]
f [] = []
f xs = let square a = a * a 
           one      = 1 
           (y:ys)   = xs 
       in (square y + one) : f ys 

-- where
g :: Int -> Int
g n | check3 == x = x
    | check3 == y = y
    | check3 == z = z * z
                  where check3 = n `mod` 3
                        x      = 0
                        y      = 1
                        z      = 2