Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 4

Table of contents
- a 4
  - i a
    - Solution i
  - ii a
    - Solution ii
- b 4
  - i b
    - Solution i
  - ii b
    - Solution ii
- c 4
  - Solution c
- d 4
  - Solution d

Use the source's type Matrix a = [[a]]. For its nonempty rectangular matrices, the number of rows and the first row's length determine the dimensions:

dimensions :: Matrix a -> (Int,Int)
dimensions rows = (length rows, length (head rows))

addMat :: Num a => Matrix a -> Matrix a -> Matrix a
addMat a b
  | dimensions a /= dimensions b = error "addMat: incompatible sizes"
  | otherwise = [[x + y | (x,y) <- zip r s]
                         | (r,s) <- zip a b]

The outer list comprehension pairs corresponding rows; the inner one pairs corresponding entries. Checking both dimensions before using zip prevents silent truncation. Thus the result has entries $c_{ij} = a_{ij} + b_{ij}$ , the definition of matrix addition. The Num constraint supplies the addition operation.

ii

 0  0

Solution

 0  0

With dimensions as in part (i), the alternative definition is

addMat :: Num a => Matrix a -> Matrix a -> Matrix a
addMat a b
  | dimensions a /= dimensions b = error "addMat: incompatible sizes"
  | otherwise = zipWith (zipWith (+)) a b

The inner zipWith adds corresponding entries; the outer one applies that row operation to corresponding rows. This computes the same matrix addition, with the same rejection of unequal dimensions. Under the valid-input assumptions, either implementation takes

Θ (mn)

unit-cost arithmetic work for

m \times n

inputs.

b

 0  0

i

 0  0

Solution

 0  0

A recursive transpose removes the first column, then transposes the remaining columns:

transpose :: Matrix a -> Matrix a
transpose [] = []
transpose ([] : _) = []
transpose rows = map head rows : transpose (map tail rows)

The internal recursive calls eventually reach rows of length zero, even though the original input has positive dimensions; the second equation handles this terminating case. Rectangularity ensures that the rows become empty together, so no head or tail is applied to an empty row in the third equation. The output is an $n \times m$ matrix with entry $b_{ji} = a_{ij}$ . The element type is unrestricted.

ii

 0  0

Solution

 0  0

Build columns by prepending the first row's entries to the columns obtained from the remaining rows:

transpose :: Matrix a -> Matrix a
transpose [] = []
transpose [row] = map (:[]) row
transpose (row : rows) = zipWith (:) row (transpose rows)

The singleton case turns each entry into a one-element column. In the recursive case, transpose rows has exactly as many columns as row has entries, so zipWith (:) extends every column once. Structural induction on the number of rows proves that each output column contains the corresponding input entries in order. This uses list zip to implement the transpose, without requiring Num a.

c

 0  0

Solution

 0  0

Reuse dimensions and either transpose definition above:

multMat :: Num a => Matrix a -> Matrix a -> Matrix a
multMat a b
  | colsA /= rowsB = error "multMat: incompatible sizes"
  | otherwise = [[sum (zipWith (*) row col) | col <- columnsB]
                                           | row <- a]
  where
    (_,colsA) = dimensions a
    (rowsB,_) = dimensions b
    columnsB = transpose b

For

A

of size

m \times n

and

B

of size

n \times p

, every selected row and column has length

n

. Their dot product is

(A B)_{ij} = k = 1 \sum n a_{ik} b_{kj} .

(1)

The two list comprehensions place this entry in row

i

, column

j

of an

m \times p

result. The dimension guard checks exactly the compatibility condition for matrix multiplication. The shared columnsB avoids recomputing the transpose for each row; the arithmetic cost is

Θ (mn p)

in the unit-cost model.

d

 0  0

Solution

 0  0

Generate successive matrix powers and take cumulative sums using matrix addition:

seriesMat :: Num a => Matrix a -> [Matrix a]
seriesMat m = scanl1 addMat (iterate (multMat m) m)

For the stipulated square matrix, iterate (multMat m) m produces m, m*m, m*(m*m), and so on. Associativity of exact matrix multiplication identifies these as

M, M^{2}, M^{3}, \dots

. The left scan scanl1 addMat then returns

[M, M + M^{2}, M + M^{2} + M^{3}, \dots] .

(1)

All dimensions remain compatible. The infinite outer list is available a finite prefix at a time under lazy evaluation; no convergence of the matrix geometric series is needed. With floating-point entries, the expression specifies this particular multiplication and addition order, since machine arithmetic need not obey the exact algebraic laws.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 4

a

i

Solution

ii

Solution

b

i

Solution

ii

Solution

c

Solution

d

Solution

 Ancestors (10)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 4

 Discussion (0)  Subscribe (1) New discussion

 Discussion (0) New discussion