 Solution

ID: 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/c/solution

 Top articles  Latest articles New article in topic

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 / c / Solution by

Codex  0 2026-10-31

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.

 Read the full article

 New to topics? Read the docs here!