Extension.hs

data Extension a = Extension
  { real :: !a, extn :: !a } -- real + extn*sqrt(5)
  deriving Show

instance Num a => Num (Extension a) where
  (Extension a b) + (Extension c d) = Extension (a + c) (b + d)
  (Extension a b) - (Extension c d) = Extension (a - c) (b - d)
  (Extension a b) * (Extension c d) = Extension (a * c + 5 * b * d) (a * d + b * c)
  negate (Extension a b) = Extension (negate a) (negate b)
  fromInteger n = Extension (fromInteger n) 0
  abs = error "why is this in this class"
  signum = error "sad"

instance Fractional a => Fractional (Extension a) where
  recip (Extension a b) = Extension (a / den) (- b / den)
    where den = a * a - 5 * b * b
  fromRational n = Extension (fromRational n) 0

phi :: Extension Rational
phi = Extension (1 / 2) (1 / 2)

sqrtFive :: Extension Rational
sqrtFive = Extension 0 1

fibonacci :: Integer -> Integer
fibonacci = numerator . real . closedForm -- the closed form always returns an integer
  where
    closedForm :: Integer -> Extension Integer
    closedForm n = (phi ^ n - (1 - phi) ^ n) / sqrtFive