This Gist contains some useful matrix operations such as addition, subtraction, exponentiation, etc.

Matrix.hs

module Matrix where

import Data.List (transpose)

newtype Matrix = Matrix [[Integer]] deriving (Show, Eq)

mFromList :: [[Integer]] -> Matrix
mFromList lst = Matrix lst

mToList :: Matrix -> [[Integer]]
mToList (Matrix mA) = mA

mtranspose :: Matrix -> Matrix
mtranspose (Matrix mA) = Matrix $ transpose mA

msize :: Matrix -> (Int, Int)
msize (Matrix mA) = (length mA, length $ head mA)

mzero :: (Int, Int) -> Matrix
mzero (rows, cols) = Matrix $ [[0 | _<-[1 .. cols]] | _<-[1 .. rows]]

madd :: Matrix -> Matrix -> Matrix
madd (Matrix mA) (Matrix mB) = Matrix $ zipWith (zipWith (+)) mA mB

msub :: Matrix -> Matrix -> Matrix
msub (Matrix mA) (Matrix mB) = Matrix $ zipWith (zipWith (-)) mA mB

mmul :: Matrix -> Matrix -> Matrix
mmul (Matrix mA) (Matrix mB) = Matrix $ [[sum $ zipWith (*) aR bC | bC<-transpose mB] | aR<-mA]

mpow :: Matrix -> Integer -> Matrix
mpow mA 0      = mzero $ msize mA
mpow mA 1      = mA
mpow mA power
  | even power = (mA `mpow` divPower) `mmul` (mA `mpow` divPower)
  | otherwise  = mA `mmul` (mA `mpow` divPower) `mmul` (mA `mpow` divPower)
  where divPower = power `div` 2

{-
 - To make a matrix:
 -    Matrix [row1, row2, row3, ..., rowN]
 -    id3x3 =  Matrix [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
 - 
 - To make a matrix from a list (synonym for Matrix constructor)
 -    mFromList [...]
 -    mFromList [[1, 2], [2, 4]] == Matrix [[1, 2], [2, 4]]
 -
 - To extract the data from a matrix:
 -    mToList $ Matrix [...]
 -    mToList $ Matrix [[1, 2], [2, 4]] == [[1, 2], [2, 4]]
 - 
 - To transpose a matrix:
 -    mtranspose $ Matrix [...]
 -    Matrix [[1, 2, 3]] == (mtranspose $ Matrix [[1, 2, 3]])
 - 
 - To get the size of a matrix:
 -    msize $ Matrix [...] -- returns (rowN, colN)
 -    msize $ Matrix [[1, 2], [3, 4]] == (2, 2)
 - 
 - To make a matrix of 0s:
 -    mzero (rowN, colN)
 -    mzero $ msize $ Matrix [[1, 2], [3, 4]] == Matrix [[0, 0], [0, 0]]
 - 
 - To add matrices:
 -    Matrix [...] `madd` Matrix [...]
 -    Matrix [[1, 1]] `madd` Matrix [[2, 3]] == Matrix [[3, 4]]
 - 
 - To subtract matrices:
 -    Matrix [...] `msub` Matrix [...]
 -    Matrix [[2, 3]] `msub` Matrix [[1, 1]] == Matrix [[1, 2]]
 - 
 - To multiply matrices:
 -    Matrix [...] `mmul` Matrix [...]
 -    Matrix [[1, 2], [3, 4]] `mmul` Matrix [[2, 2], [2, 2]] == Matrix [[6, 6], [14, 14]]
 - 
 - To raise a matrix to a power
 -    Matrix [...] `mpow` power
 -    Matrix [[2, 4]] `mpow` 5 == Matrix [[32, 64]]
 - 
 - Some notes:
 - These functions (especially `mmul`), read the matrix row by row. This can affect you when when you're trying to multiply a matrix
 - by a column. For example:
 - 
 -    Matrix [[1, 1, 1], [2, 2, 2], [3, 3, 3]] `mmul` Matrix [[2, 4, 6]]  ==  Matrix [[2, 4, 6], [4, 8, 12], [6, 12, 18]]
 - 
 - The second matrix is interpreted as one row, 1 by 3 matrix, instead of a 3 by 1 matrix. To use a 3 by 1 matrix, we need to 
 - put each element into its own row:
 - 
 -    Matrix [[1, 1, 1], [2, 2, 2], [3, 3, 3]] `mmul` Matrix [[2], [4], [6]]  ==  Matrix [[12], [24], [36]]
 -
 - and if our data requires a 1 by 3 matrix, we can `mtranspose` the result.
-}

Here's an example to generate Padovan numbers.

import Matrix

getPadovan :: Integer -> Integer
getPadovan 0 = 1
getPadovan n = last $ last $ mToList $ (padovanMatrix `mpow` n) `mmul` initialMatrix
  where padovanMatrix = Matrix [[0, 1, 1], [1, 0, 0], [0, 1, 0]]
        initialMatrix = Matrix [[1], [1], [1]]

The nice thing about mpow is that it handles getPadovan 1 and getPadovan 2 for us in this case.
This function is quite simple to understand and makes it look "cute" because we don't need to worry about the workings of mmul and mpow.

There can be improvements, but I guess not many people would like to compute 10^10th Padovan number.. 😅 From what I discovered, the 1,000,000th Padovan number has 122,124 digits 😲