Use a technique similar to fast exponentiation for repeatedly `mappend`ing the same monoid

fastMappend.hs

import Data.Monoid
import Data.Function (on)
import System.Environment

-- | Apply repeatedly `mappend` on a monoid
-- | Uses the associativity and the identity element of monoids
fastMappend :: (Monoid a) => a -> Integer -> a
fastMappend x n = iter x n mempty
  where iter :: (Monoid a) => a -> Integer -> a -> a
        iter _ 0 acc = acc
        iter x n acc = if even n 
                           then iter (x `mappend` x) (n `div` 2) acc
                           else iter x (n-1) (x `mappend` acc)

-- | Fast exponentiation using the Product monoid
fastExp :: (Num a) => a -> Integer -> a
fastExp x n = getProduct $ fastMappend (Product x) n

-- | Fibonnaci using matrix multiplication (which forms a monoid)
fastFib :: Integer -> Integer
fastFib n = (\(_, x, _, _) -> x) $ getMatrix $ fastMappend (MatrixMult (1,1,1,0)) n

-- | Returns a repeatedly applied function of type (a -> a) (uses the Endo monoid)
fastApply :: (a -> a) -> Integer -> a -> a
fastApply f n = appEndo $ fastMappend (Endo f) n

type Matrix a = (a,a,
                 a,a) 

newtype MatrixMult a = MatrixMult { getMatrix :: Matrix a }

-- Matrix operations
mult :: Num a => Matrix a -> Matrix a -> Matrix a
mult (a,b,c,d) (e,f,g,h) = 
        (a*e + b*g, a*f + b*h,
         c*e + d*g, c*f + d*h)
instance Num a => Semigroup (MatrixMult a) where
        m1 <> m2 = MatrixMult $ (mult `on` getMatrix) m1 m2

instance Num a => Monoid (MatrixMult a) where
        mempty = MatrixMult (1,0,0,1)

main :: IO ()
main = do 
    n <- getArgs
    print $ fastFib (read $ head n)