#!/usr/bin/runghc

module AlgExp where

import Data.Bits

-- |
-- >>> expFun 2 3
-- 8
expFun :: Integer -> Int -> Integer
expFun b n = product (replicate n b)

-- |
-- >>> expRec 2 3
-- 8 % 1
expRec :: Rational -> Integer -> Rational
expRec b n
  | n == 0 = 1
  | 0 < n = b * expRec b (n - 1)
  | otherwise = 1 / expRec b (-n)

-- |
-- >>> expEff 2 3
-- 8
expEff :: Integer -> Integer -> Integer
expEff b n
  | n == 1 = b
  | n .&. 1 == 0 = expEff (b * b) (div n 2)
  | otherwise = b * expEff (b * b) (div n 2)

main :: IO ()
main = do
  print (expRec 2 3)
  print (expFun 2 3)
  print (expEff 2 3)