Matrix multiplication (Haskell)

From LiteratePrograms
Jump to: navigation, search
Other implementations: Haskell | Python


[edit] Using nested lists


module MMList where

import Data.List

-- We can represent vectors as lists of numbers, and matrices as lists of row
-- vectors. This is a simple solution, but it lacks type safety and is
-- inefficient compared to possible uses of Haskell's arrays.
type Vector a = [a]
type Matrix a = [Vector a]

[edit] Vector-by-vector dot product


-- The dot product of vectors u and v, i.e. the sum of the products of
-- corresponding entries. Will be used to define the matrix-by-vector product.
mulVV :: Num a => Vector a -> Vector a -> a
mulVV u v = sum $ zipWith (*) u v

[edit] Matrix-by-vector product


-- Matrix m right-multiplied by column vector v, i.e. a row vector containing
-- the dot product of each row of m with v.
-- Will be used to define the matrix-by-matrix product.
mulMV :: Num a => Matrix a -> Vector a -> Vector a
mulMV m v = map (mulVV v) m

[edit] Matrix-by-matrix product


-- Matrix m right-multiplied by matrix n, i.e. the matrix n after each of its
-- columns has been left-multiplied by m.
mulMM :: Num a => Matrix a -> Matrix a -> Matrix a
mulMM m n = transpose $ map (mulMV m) $ transpose $ n

[edit] Example program


module MMListExample where

import MMList
import Control.Monad

-- Compute the Fibonacci sequence by repeated matrix multiplication.
-- See: <>
-- and: <>.

idM2 = [[1, 0],
        [0, 1]]

fibQ = [[1, 1],
        [1, 0]]

fibs :: [Matrix Integer]
fibs = iterate (mulMM fibQ) idM2

main = forM_ fibs $ \m -> print m >> putStrLn "Press Return" >> getLine

[edit] Running

To use Hugs instead of GHC, substitute hugs for ghci, and runhugs for runghc.

[edit] MMList.hs

Matrix_multiplication_(Haskell)$ ls
MMListExample.hs  MMList.hs

Matrix_multiplication_(Haskell)$ ghci MMList.hs
GHCi, version 7.6.3:  :? for help
[1 of 1] Compiling MMList           ( MMList.hs, interpreted )
Ok, modules loaded: MMList.
*MMList> mulMM [[0,0,1],[1,0,0],[0,1,0]] [[1,2],[3,4],[5,6]]

[edit] MMListExample.hs

Matrix_multiplication_(Haskell)$ runghc MMListExample.hs 
Press Return

Press Return

Press Return

Press Return

Press Return

Press Return
Download code