Find main diagonal in matrix - Scheme

问题:

I need to extract the main diagonal from a square matrix

(1 2 3)
(4 5 6) -> (1 5 9)
(7 8 9)

I have the following code and I need to replace the ... with the appropriate functions.

(define (diag m)
  (if (null? m) '()
      (cons (... m)
            (diag (map ... (... m))))))

Input: (diag '((1 2 3) (4 5 6) (7 8 9))) Output: (1 5 9)

Any ideas? Thank you!

回答1:

So you are asking, given you have the list '((1 2 3) (4 5 6) (7 8 9)) how do I get the value 1 from it?

Then you are asking given the same list, how do I get ((4 5 6) (7 8 9)) from it.

Then given that result how do I make a new list using map that only takes the rest of each element list so that the result is ((5 6) (8 9))

The question code looks like came from SO as an answer with VERY easy challenge on how to complete it. Am I right?

The answer is of course just list accessors every beginner schemer should know: cdr x 2 and caar, not necessarily in that order.

回答2:

First of all I created a function that returns n-th element of list (I am not sure if you can use built-in function for it, that's why I created my own bicycle):

(define (nthItem l item currentItem)
    (if (null? l) '()
      (if (= currentItem item) (car l)
        (nthItem (cdr l) item (+ currentItem 1)))))

Then I created a function that you need. I added a parameter "i" that contains current position on a diagonal:

(define (diagPrivate m i)
  (if (null? m) '()
    (cons (nthItem (car m) i 0)
      (diagPrivate (cdr m) (+ i 1)))))

For better appearance I created a wrapper for this function (that looks like your initial function):

(define (diag m)
    (diagPrivate m 0))

回答3:

Using Racket which is a Scheme dialect:

(define diag '((1 2 3) (4 5 6) (7 8 9)))

(define (getDiagonal l)
  (let loop ((l l)
             (ol '())
             (n 0))
    (cond
      [(empty? l) (reverse ol)]
      [(loop (rest l) 
             (cons (list-ref (first l) n) ol) 
             (add1 n))])))

(getDiagonal diag)

Output:

'(1 5 9)

There is for/list loop in Racket which also can be used here:

(for/list ((i (length diag)))
  (list-ref (list-ref diag i) i))