Exercise 150 - Transposing a Matrix

Mathematics teachers may have introduced you to matrix calculations by now. Numeric programs deal with those, too. Here is one possible data representation for matrices:

; A Matrix is one of:

; – empty

;; – (cons LN Matrix)

; An LN is one of:

; – empty

;; – (cons Number LN)

; interp. a matrix is a list of rows, a row is a list of numbers

; constraint: all rows are of the same length

Study it and translate the two-by-two matrix consisting of the numbers 11, 12, 21, 22 into this data representation.

They don't make it 100% clear how this should translate to a matrix (eg horizontally or vectically), but common sense would be to divide it into two horizontal rows

(require racket/base)

(define MATRIX (list (list 11 12)

(list 21 22)))

; define an extra couple of Matrix's to use for testing.

(define MATRIX2 (list (list 11 12)

(list 21 22)

(list 31 32)))

(define MATRIX3 (list (list 11 12 13)

(list 21 22 23)

(list 31 32 33)))

Study it and translate the two-by-two matrix consisting of the numbers 11, 12, 21, 22 into this data representation.

The following function implements the important mathematical operation of transposing the entries in a matrix. To transpose means to mirror the entries along the diagonal, that is, the line from the top-left to the bottom-right.

; Matrix -> Matrix

; transpose the items on the given matrix along the diagonal

;(check-expect (transpose mat1) tam1)

(define (transpose lln)

  (cond

    [(empty? (first lln)) empty]

    [else (cons (first* lln) (transpose (rest* lln)))]))

The definition assumes two auxiliary functions:

first*, which consumes a matrix and produces the first column as a list of numbers;;

rest*, which consumes a matrix and removes the first column. The result is a matrix.

Even though you lack definitions for these functions, you should be able to understand how transpose works. You should also understand that you cannot design this ;function with the design recipes you have seen so far. Explain why.

Design the two “wish list” functions. Then complete the design of the transpose with some test cases. 

I am not at all sure how transpose works at this point! (My maths-fu is weak). From reading the code, it seems to work thru a list of lists of numbers, taking the first column and then creating a new list by adding this first column back onto the start of the matrix (which has just had the first column removed!

(An example here would have gone a long way.)

Even if this is transposing the colums, it seems it would be working in complete columns, so I'm not sure how it could ever produce a diagonal transposition.

To confound things further, they say "You cannot design this function". then without explaining anything further, they tell us to go design this function!

I'm not sure if i'm meant to be able to do this or not, but we'll have a try... If we can run the code and it does what they say, perhaps seeing it in process may make things clearer!

The function first* is not too hard - it's the standard recursive scheme function. If the matrix is empty, return empty, otherwise build up a new list consisting of the first number in the list, and the result of calling this on the *rest* of the rows in the matrix

;first* consumes a matrix and produces the first column as a 

;list of numbers

; Matrix -> LN

(define (first* lln)

  (cond ((empty? lln) empty)

        ((cons? lln) (cons (first (first lln)) 

                           (first* (rest lln))))))  

(check-expect (first* MATRIX) (list 11 21))

(check-expect (first* MATRIX2) (list 11 21 31))

This is basically the inverse of first* - this time we want to grab the rest of each list and return that.

;Matrix -> Matrix

(define (rest* lln)

  (cond ((empty? lln) empty)

        ((cons?  lln) (cons (rest (first lln))

                            (rest* (rest lln))))))

(check-expect (rest* MATRIX) (list (list 12) 

                                   (list 22)))

(check-expect (rest* MATRIX2) (list (list 12) 

                                    (list 22) 

                                    (list 32)))

(check-expect (rest* MATRIX3) (list (list 12 13)

                                    (list 22 23) 

                                    (list 32 33)))

Now to test the transposing - in theory, this function should turn our matrix from this:

; 11 12 13

; 21 22 23

; 31 32 32

into this:

; 11 21 31

; 12 22 32

; 13 23 33

(check-expect (transpose MATRIX3) (list (list 11 21 31)

                                        (list 12 22 32)

                                        (list 13 23 33)))

The test passes, so the transpose function does what it is meant to – but why?!?! 

Let's add a  debugging method to try and work out what's going on.

(define (print-matrix mat)

  (cond ((empty? mat) 

         (fprintf (current-output-port) " *** \n"))

        (else (fprintf (current-output-port) 

                       " ~a\n" 

                       (first mat))

              (print-matrix (rest mat)))))

If you put this into the (transpose) function, you can see that transpose does rip the matrix apart into columns. Once the columns have been removed, these get cons'd together horizontally (as rows) to become the new Matrix. This automatically 'mirrors' each half along the diagonal without needing to work on diagonal sections of the matrix.

For example, originally if you had:

; (list (list 2 5)

;       (list 8 9))

This would get ripped into the two colums (list 2 8) and (list 8 9) and then assembled as;

; (list (list 2 8)

;       (list 8 9))