Matrix Operations
June 22, 2010
All of these operations rely heavily on loops using the for syntax given in the Standard Prelude. Here is addition:
(define (matrix-add a b)
(let ((ar (matrix-rows a)) (ac (matrix-cols a))
(br (matrix-rows b)) (bc (matrix-cols b)))
(if (or (not (= ar br)) (not (= ac bc)))
(error 'matrix-add "incompatible matrices")
(let ((c (make-matrix ar ac)))
(for (i ar)
(for (j ac)
(matrix-set! c i j
(+ (matrix-ref a i j)
(matrix-ref b i j)))))
c))))
Multiplying a matrix by a scalar is just as simple. Note that the scalar, as well as the matrix elements, can be any numeric type:
(define (matrix-scalar-multiply n a)
(let* ((ar (matrix-rows a))
(ac (matrix-cols a))
(c (make-matrix ar ac)))
(for (i ar)
(for (j ac)
(matrix-set! c i j
(* n (matrix-ref a i j)))))
c))
Multiplying two matrices involves a third for
loop:
(define (matrix-multiply a b)
(let ((ar (matrix-rows a)) (ac (matrix-cols a))
(br (matrix-rows b)) (bc (matrix-cols b)))
(if (not (= ac br))
(error 'matrix-multiply "incompatible matrices")
(let ((c (make-matrix ar bc 0)))
(for (i ar)
(for (j bc)
(for (k ac)
(matrix-set! c i j
(+ (matrix-ref c i j)
(* (matrix-ref a i k)
(matrix-ref b k j)))))))
c))))
Transposing a matrix involves no arithmetic at all, just subscript manipulations:
(define (matrix-transpose a)
(let* ((ar (matrix-rows a))
(ac (matrix-cols a))
(c (make-matrix ac ar)))
(for (i ar)
(for (j ac)
(matrix-set! c j i
(matrix-ref a i j))))
c))
Here are some examples:
> (define a #(#(1)
#(2)
#(3)))
> (define b #(#(1 2 3)
#(4 5 6)))
> (define c #(#(2 3 4)
#(3 4 5)))
> (define d #(#(1 2 3 4)
#(2 3 4 5)
#(3 4 5 6)))
> (matrix-add b c)
#2(#3(3 5 7)
#3(7 9 11))
> (matrix-scalar-multiply 2 b)
#2(#3(2 4 6)
#3(8 10 12))
> (matrix-multiply b d)
#2(#4(14 20 26 32)
#4(32 47 62 77))
> (matrix-transpose b)
#3(#2(1 4)
#2(2 5)
#2(3 6))
We used the matrix operations and for
operator from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/5nzWMChE.
[…] Praxis – Matrix Operations By Remco Niemeijer In today’s Programming Praxis exercise our task is to implement four common matrix operations. The provided […]
My Haskell solution (see http://bonsaicode.wordpress.com/2010/06/22/programming-praxis-matrix-operations/ for a version with comments):
Here’s my Java solution.
@Remco,
Your Haskell solution is gorgeous (its simplicity astounds me). I’ll hopefully be able to churn out solutions like that in Haskell soon! =)
@Elvis Montero:
Thanks. Best of luck with learning Haskell. I can highly recommend it :)
@Remco,
Your post has inspired me to learn Haskell!
;;; A scheme solution. Nothing like the beauty of the haskell one though ;-)
;; Q1
(define (add-matrix m1 m2)
(cond ((or (null? m1) (null? m2)) ‘())
(else (cons (sum-list (car m1) (car m2))
(add-matrix (cdr m1) (cdr m2))))))
;; Q1 helper
(define (sum-list l1 l2)
(cond ((or (null? l1) (null? l2)) ‘())
(else (cons (+ (car l1) (car l2))
(sum-list (cdr l1) (cdr l2))))))
;; Q2
(define (scale s m)
(letrec ((scale* (lambda (m)
(cond ((null? m) ‘())
(else (cons (mul-list s (car m))
(scale* (cdr m))))))))
(scale* m)))
;; Q2 helper
(define (mul-list s l)
(letrec ((mul-list* (lambda (l)
(cond ((null? l) ‘())
(else (cons (* s (car l))
(mul-list* (cdr l))))))))
(mul-list* l)))
;; Q3
(define (X A B)
(cond ((null? A) ‘())
(else (cons (psum (car A) B)
(X (cdr A) B)))))
;; Q3 helper – genereate list of cross-sums
(define (psum l m)
(letrec ((psum* (lambda ™
(cond ((null? tm) ‘())
(else (cons (xs l (car tm))
(psum* (cdr tm))))))))
(psum* (transpose m))))
;; Q3 helper – multiply each element and sum result
(define (xs l1 l2)
(cond ((or (null? l1) (null? l2)) 0)
(else (+ (* (car l1) (car l2)) (xs (cdr l1) (cdr l2))))))
;; Q4
(define (transpose m)
(cond ((null? (car m)) ‘())
(else (cons (list-of-heads m)
(transpose (list-of-tails m))))))
;; Q4 helper
(define (list-of-heads m)
(cond ((null? m) ‘())
(else (cons (car (car m))
(list-of-heads (cdr m))))))
;; Q4 helper
(define (list-of-tails m)
(cond ((null? m) ‘())
(else (cons (cdr (car m))
(list-of-tails (cdr m))))))
bah.. indents lost :-(
one with proper indents on pocoo….
http://paste.pocoo.org/show/nZhGWlzvWmDhV9pRV5im/
Geir S: list-of-heads is just (map car m)
Interestingly I realized after writing it that I duplicated the Haskell version above in Scheme, though I put scalar multiplication into matrix multiplication. I have such a hard time reading Haskell that I couldn’t notice it before! No error checking. A matrix is a list of lists.
My Haskell solution:
Not nearly as sexy as @Remco’s, partly because I used a Matrix data type that complicated things somewhat unnecessarily. I wrote zipList from scratch before remembering there was a ‘transpose’ function in Data.List, but overall this was a good learning experience. I remember back when I was into C++, and I wrote some matrix classes–the header declarations alone were longer than this :-)
My Python solution with convenient operators overloading, though not very effective:
Scheme solution: