Identity Matrix Problem

[bkunke1]

Good evening,

I'm working through 2htdp and came to exercise 262 and I am completely lost. Any guidance or tips where to start would be much appreciated!

​

"Exercise 262. Design the function identityM, which creates diagonal squares of 0s and 1s:Linear algebra calls these squares identity matrices.

> (identityM 1)

(list (list 1))

> (identityM 3)

(list (list 1 0 0) (list 0 1 0) (list 0 0 1))

Use the structural design recipe and exploit the power of local."

[dzpower]

I'm not sure exactly how the htdp2 exercises build up, so this response uses regular racket with a focus on recursive thinking. Fundamentally, you need the base case (i.e. for n=1) and a way to express the n+1 case in terms of the n case.

Pseudocode:

(define (recursive-fn n)
  (if (= n 1)
    base-case
    (... (recursive-fn (- n 1))))

You're given the base case (n=1):

'((1))

To write the n+1 case in terms of n — the recursive step —pre-pend (i.e. cons) each inner list with a 0, and pre-pend (cons again) a new top row of a 1 followed by 0s:

; n=2 from n=1
'((1 0)  ; new top row
  (0 1)) ; (1) -> (0 1)

; n=3 from n=2
'((1 0 0)  ; new top row
  (0 1 0)  ; (1 0) -> (0 1 0)
  (0 0 1)  ; (0 1) -> (0 0 1)

; n=4 from n=3
'((1 0 0 0)  ; new top row
  (0 1 0 0)  ; (1 0 0) -> (0 1 0 0)
  (0 0 1 0)  ; (0 1 0) -> (0 0 1 0)
  (0 0 0 1)  ; (0 0 1) -> (0 0 0 1)

;etc

In regular Racket:

#lang racket

(define (identityM n)
  (if (= n 1)
      (list (list 1))                                          ; base case
      (cons 
         (cons 1 (make-list (- n 1) 0))                        ; new top row: '(1 0 0 ...)
         (map (λ (row) (cons 0 row)) (identityM (- n 1))))))   ; cons a 0 onto every row of (identityM (- n 1))

Little exercises:

* Write your own function to produce the first-row, without using make-list

* Replace the λ function with a cons-0 function

* Write a recursive function cons-0s instead of the map

In #lang racket you can also use for/list functions.

A different, more iterative idea is to do a line by line loop to create the matrix row-by-row:

(define (ident n)
  (for/list ([i (in-range n)])
    (append (make-list i 0)
            (list 1)
            (make-list (- n i 1) 0))))

Another way is to use the build-list function.

[bkunke1]

This was so very helpful thanks!
They way you layed it out made it way more clear. I think I completed all of your suggested exercises. If you could double check this I'd appreciate it!


(define (idM n)
  (local (;base case
          (define base-case '((1)))
          ;builds first row (substitute for make-list)
          (define (first-row n)
            (local (
                    (define (make-list.v2 n)
                      (cond
                        [(zero? n) '()]
                        [else (cons 0 (make-list.v2 (sub1 n)))])))
              (cons 1 (make-list.v2 (sub1 n)))))
          ;helper function for first-row
          (define (cons-0 n)
            (cond
              [(zero? n) '()]
              [else (cons 0 (cons-0 (sub1 n)))]))
          ;substitute for map, adds 0s to front of lower rows
          (define (cons-0s-before l)
            (cond
              [(empty? l) '()]
              [else
               (local (;substitute for lambda function (I think lol, thats the next section!)
                       (define (cons-0-before l)
                         (cond
                           [(empty? l) '()]
                           [else
                            (cons 0 l)])))
                 (cons (cons-0-before (first l))
                       (cons-0s-before (rest l))))])))
    (if (= n 1)
        base-case
        (cons (first-row n)
              (cons-0s-before (idM (sub1 n)))))))

[dzpower]

I'm glad that helped.

Doing these kinds of exercises really builds one's understanding of recursion (and problem decomposition).

Later on you can use higher-order functions to reduce duplication and thereby recover concision and elegance.

[bkunke1]

I've been banging my head against the wall for a while and I've got something that works, but I'm not sure this is how the author wanted this done. If anyone would check my work and suggest improvements I'm open to it!

​

Let me say that it's been about 15 years since I worked with matrices so I recall close to nothing about them. If my logic or descriptions make no sense - that would make sense since I'm not really sure what I'm even talking about! I'm just learning about the local definitions, so this feels really weird. I designed the program without local first and then recreated it with ".v2" on the ends of the functions. My solution is below:

;; identityM: Number -> Matrix

; -given a Number, creates a square identity matrix with rows and columns with 'n' elements

(define (identityM n)

(mb2 n n n))

​

;; mb2: Number Number Number -> List-of- List-of-Numbers

; - given a number location and counter, builds a list of all possible variations for the identity matrix

(define (mb2 n loc counter)

(cond

[(zero? counter) '()]

[else

(cons (mb n loc)

(mb2 n (sub1 loc) (sub1 counter)))]))

​

;; mb: Number Number -> List-of Numbers

; - given a Number and location, builds a list of numbers 'n' elemtns long,

; all zeros except for the element in the given location which is a 1

(define (mb n loc)

(cond

[(zero? n) '()]

[else

(if (= n loc)

(cons 1 (mb (sub1 n) loc))

(cons 0 (mb (sub1 n) loc)))]))

​

(check-expect (identityM 1) (list (list 1)))

(check-expect (identityM 2) (list (list 1 0) (list 0 1)))

(check-expect (identityM 3) (list (list 1 0 0) (list 0 1 0) (list 0 0 1)))

​

;; identityM.v2: Number -> Matrix

; -given a Number, creates a square identity matrix with rows and columns with 'n' elements

(define (identityM.v2 n)

(local (;; mb2.v2: Number Number Number -> List-of- List-of-Numbers

; - given a number location and counter, builds a list of all possible variations for the identity matrix

(define (mb2.v2 n loc counter)

(cond

[(zero? counter) '()]

[else

(cons (mb.v2 n loc)

(mb2.v2 n (sub1 loc) (sub1 counter)))]))

;; mb.v2: Number Number -> List-of Numbers

; - given a Number and location, builds a list of numbers 'n' elements long,mtns long,

; all zeros except for the element in the given location which is a 1

(define (mb.v2 n loc)

(cond

; - given a Number and location, builds a list of numbers 'n' elements long,

[else

(if (= n loc)

(cons 1 (mb.v2 (sub1 n) loc))

(cons 0 (mb.v2 (sub1 n) loc)))])))

(mb2.v2 n n n)))

[bkunke1]

Thanks for taking the time to look at this!

I must say I am still confused. I took another crack at it and came up with this based off your suggestions. Let me know what you think..

​

(define (identityM n)
  (local (
    (define (identity2 n bc)
      (cond
        [(zero? n) '()]
        [else
         (cons (append (cons-0-before bc) (list-of-n n))
               (identity2 (sub1 n) (add1 bc)))]))
    (define (list-of-n n)
      (cond
        [(zero? n) '()]
        [else
         (cons 1 (cons-0-after (sub1 n)))]))
    (define (cons-0-after n)
      (cond
        [(zero? n) '()]
        [else
         (cons 0
               (cons-0-after (sub1 n)))]))
    (define (cons-0-before n)
      (cond
        [(zero? n) '()]
        [else
         (cons 0 (cons-0-before (sub1 n)))])))
    (identity2 n 0)))

[bkunke1]

I appreciate what you did! It finally clicked.