45 lines
1.2 KiB
Haskell
45 lines
1.2 KiB
Haskell
import Data.List (transpose)
|
|
|
|
fib
|
|
:: (Integral b, Num a)
|
|
=> b -> a
|
|
fib 0 = 0 -- this line is necessary because "something ^ 0" returns "fromInteger 1", which unfortunately
|
|
-- in our case is not our multiplicative identity (the identity matrix) but just a 1x1 matrix of 1
|
|
fib n = (last . head . unMat) (Mat [[1, 1], [1, 0]] ^ n)
|
|
|
|
-- Code adapted from Matrix exponentiation operator task ---------------------
|
|
(<+>)
|
|
:: Num c
|
|
=> [c] -> [c] -> [c]
|
|
(<+>) = zipWith (+)
|
|
|
|
(<*>)
|
|
:: Num a
|
|
=> [a] -> [a] -> a
|
|
(<*>) = (sum .) . zipWith (*)
|
|
|
|
newtype Mat a = Mat
|
|
{ unMat :: [[a]]
|
|
} deriving (Eq)
|
|
|
|
instance Show a =>
|
|
Show (Mat a) where
|
|
show xm = "Mat " ++ show (unMat xm)
|
|
|
|
instance Num a =>
|
|
Num (Mat a) where
|
|
negate xm = Mat $ map (map negate) $ unMat xm
|
|
xm + ym = Mat $ zipWith (<+>) (unMat xm) (unMat ym)
|
|
xm * ym =
|
|
Mat
|
|
[ [ xs Main.<*> ys -- to distinguish from standard applicative operator
|
|
| ys <- transpose $ unMat ym ]
|
|
| xs <- unMat xm ]
|
|
fromInteger n = Mat [[fromInteger n]]
|
|
abs = undefined
|
|
signum = undefined
|
|
|
|
-- TEST ----------------------------------------------------------------------
|
|
main :: IO ()
|
|
main = (print . take 10 . show . fib) (10 ^ 5)
|