Matrix multiplication (Haskell)

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

Contents

[edit] Using nested lists

<<MMList.hs>>=

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

<<MMList.hs>>=

--------------------------------------------------------------------------------
-- 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

<<MMList.hs>>=

--------------------------------------------------------------------------------
-- 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

<<MMList.hs>>=

--------------------------------------------------------------------------------
-- 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

<<MMListExample.hs>>=

module MMListExample where

import MMList
import Control.Monad

---------------------------------------------------------------------------------
-- Compute the Fibonacci sequence by repeated matrix multiplication.
-- See: <http://mathworld.wolfram.com/FibonacciQ-Matrix.html>
-- and: <http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form>.

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: http://www.haskell.org/ghc/  :? 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]]
[[5,6],[1,2],[3,4]]

[edit] MMListExample.hs

Matrix_multiplication_(Haskell)$ runghc MMListExample.hs 
[[1,0],[0,1]]
Press Return

[[1,1],[1,0]]
Press Return

[[2,1],[1,1]]
Press Return

[[3,2],[2,1]]
Press Return

[[5,3],[3,2]]
Press Return

[[8,5],[5,3]]
Press Return
^C
Matrix_multiplication_(Haskell)$
Download code
hijacker
hijacker
hijacker
hijacker