Multiplying matrices using functional programming
16th October 2024
The most efficient way to represent matrices in Common Lisp is as two-dimensional arrays, and there are matrix libraries that work with matrices in this representation.
However, for simple applications it's convenient to represent matrices as lists of lists. This has the advantage that operations such as matrix multiplication can be written very simply in a functional way, by building up the following functions transpose, dot, columns, and multiply.
Representing matrices
For example, a 4 x 3 matrix A would be represented as a list of lists as follows:
(defparameter a '((1 0 1) (2 1 1) (0 1 1) (1 1 2)))
A 3 x 3 matrix B would be represented:
(defparameter b '((1 2 1) (2 3 1) (4 2 2)))
Transpose
The first function we need is transpose, which flips a matrix around its diagonal, converting an n x m matrix into an m x n matrix. This can be written:
(defun transpose (lst) (apply #'mapcar #'(lambda (&rest x) x) lst))
Testing it on the matrix A:
> (transpose a) ((1 2 0 1) (0 1 1 1) (1 1 1 2))
Dot
The next function we need is dot, which calculates the dot product of two 1 x n vectors:
(defun dot (x y) (reduce #'+ (mapcar #'(lambda (x y) (* x y)) x y)))
For example:
> (dot '(1 0 1) '(1 2 4)) 5
which is the dot product of the vectors corresponding to the first row of A and the first column of B.
Columns
Next, columns gives the matrix product of a 1 x n matrix and an n x m matrix:
(defun columns (r y) (mapcar #'(lambda (c) (dot r c)) (transpose y)))
For example:
> (multiply '((1 0 1)) b) ((5 4 3))
which multiplies the first row of A, a 1 x 3 matrix, by B, a 3 x 3 matrix, to give a 1 x 3 matrix.
Multiply
Finally, multiply combines these functions to multiply two arbitrary matrices:
(defun multiply (x y) (mapcar #'(lambda (r) (columns r y)) x))
Trying it with our two original matrices:
> (multiply a b) ((5 4 3) (8 9 5) (6 5 3) (11 9 6))
which gives the correct 4 x 3 matrix product.
The full set of functions
Here's the full set of functions to implement matrix multiplication:
(defun transpose (lst) (apply #'mapcar #'(lambda (&rest x) x) lst)) (defun dot (x y) (reduce #'+ (mapcar #'(lambda (x y) (* x y)) x y))) (defun columns (r y) (mapcar #'(lambda (c) (dot r c)) (transpose y))) (defun multiply (x y) (mapcar #'(lambda (r) (columns r y)) x))
blog comments powered by Disqus