import Html exposing (..)

{-  Function "expt" computes b^n (b raised to power n) using 
    backward linear recursion.

    Time complexity:  O(n) recursive calls
    Space complexity: O(n) active recursive calls
    Termination: Argument decreases by 1 toward 0 in 
                 recursive call
		 
-}

expt : Int -> Int -> Int
expt b n =
   if n == 0 then
      1
   else if n > 0 then
      b * expt b (n-1)  -- backward recursion
   else
      0
 
{-  Function "expt2" computes b^n using tail recursion.  

    Time complexity:  O(n) recursive calls 
    Space complexity: O(1) with tail call optimization 
    Termination:      Argument m of expt_iter decreases by 1 
                      toward 0 inrecursive call
-}

expt2 : Int -> Int -> Int
expt2 b n =
   let
      exptIter m p =
         if m == 0 then
            p  
         else
            exptIter (m-1) (b*p) -- tail rec
   in
      if n < 0 then
         0  -- error?
      else
         exptIter n 1

{-  Function "expt3" computes b^n using a logarithmic algorithm 
    and backward recursion.  It takes advantage of squaring.
   
        b^n = (b^(n/2)) * (b^(n/2)) if n even
        b^n = b * b^(n-1)           if n odd

     Time complexity:  O(log n) recursive calls
     Space complexity: O(log n) active recursive calls needing 
                       stack frames
     Termination:      Argument n decreases either by one-half or 
                       by 1 toward 0 on the recursive calls
-}

expt3 : Int -> Int -> Int
expt3 b n =
   let
      exptAux m =
         if m == 0 then
            1
         else if m % 2 == 0 then
            let
               exp = exptAux (m // 2)
            in 
               exp * exp       -- backward rec
         else
            b * exptAux (m-1)  -- backward rec
   in
      if n < 0 then
         0 -- error?
      else
         exptAux n

{-  Tail recursive version of logarithmic algorihm
    Borrowing James Church's good idea of squaring base
-}

expt4 : Int -> Int -> Int
expt4 b n =
   let
      exptIter base m r =
         if m == 0 then
            r
         else if m % 2 == 0 then
            exptIter (base * base) (m // 2) r
         else
            exptIter base (m-1) (base * r)                   
   in
      if n < 0 then
         0 -- error?
      else
         exptIter b n 1
 
-- Simple Display Functions

newline = br [] []

displayLines : List String -> List (Html msg)
displayLines ss = 
   case ss of
      []      -> []
      x :: xs -> text x :: newline :: displayLines xs

display : List String -> Html msg
display ls = p [] (displayLines ls)

-- Some testing

main =
  display 
     [ toString (expt2 3 3)
     , toString (expt2 3 3)
     , toString (expt3 3 3)
     , toString (expt4 3 3)
     , "Done!"
     ]