Efficient fibonacci numbers using infinite precision integer arithmetic

fibonacci.hs

import Numeric.Natural (Natural)

import qualified Data.Semigroup

-- | @fibonacci n@ computes the @nth@ fibonacci number efficiently using infinite
-- precision integer arithmetic
-- 
-- Try @fibonacci 1000000@
fibonacci :: Natural -> Natural
fibonacci n = x01 (Data.Semigroup.mtimesDefault n m)
  where
    m = Matrix_2x2
            { x00 = 0, x01 = 1
            , x10 = 1, x11 = 1
            }

data Matrix_2x2 =
    Matrix_2x2
        { x00 :: Natural, x01 :: Natural
        , x10 :: Natural, x11 :: Natural
        }

instance Monoid Matrix_2x2 where
    mempty =
        Matrix_2x2
            { x00 = 1, x01 = 0
            , x10 = 0, x11 = 1
            }

    mappend l r =
        Matrix_2x2
            { x00 = x00 l * x00 r + x01 l * x10 r, x01 = x00 l * x01 r + x01 l * x11 r
            , x10 = x10 l * x00 r + x11 l * x10 r, x11 = x10 l * x01 r + x11 l * x11 r
            }