バイナリ法によるフィボナッチ数の計算。

gistfile1.txt

import Data.Semigroup
import Numeric.Natural.Internal

-- 2x2 integer matrix [[a,b],[c,d]]
data Mat2x2 a = Mat2x2 a a a a deriving (Show,Eq)

-- multiply matrix [[a,b],[c,d]] . [[p,q],[r,s]] = [[a*p+b*r, a*q+b*s],[c*p+d*r, c*q+d*s]]
multiply_mat2x2 :: Num a => Mat2x2 a -> Mat2x2 a -> Mat2x2 a
multiply_mat2x2 (Mat2x2 a b c d) (Mat2x2 p q r s) = Mat2x2 (a*p+b*r) (a*q+b*s) (c*p+d*r) (c*q+d*s)

instance Num a => Monoid (Mat2x2 a) where
    mempty  = Mat2x2 1 0 0 1
    mappend = multiply_mat2x2

-- ported from semigroups-0.9.2
timesN :: (Whole n, Monoid a) => n -> a -> a
timesN n x | n == 0    = mempty
           | otherwise = unwrapMonoid . times1p (unsafePred n) . WrapMonoid $ x

-- fib n is (1,0) element of [[1,1],[1,0]]^n
fib :: Num a => Natural -> a
fib n = case timesN n (Mat2x2 1 1 1 0) of Mat2x2 _ _ c _ -> c

main = print $ fib 10000