Find main diagonal in matrix - Scheme

Question

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!

The input is only one parameter - a list of lists. Example: (diag '((1 2 3) (4 5 6) (7 8 9))) — K. H., Dec 23 '16 at 11:07
Are you sure that we need just to replace the sequence "..." ? I found another solution that I can show you. — Roman Podymov, Dec 23 '16 at 11:30
Yes, you should replace "...". But if you have found out another solution, it would be interesting for me how it works :) — K. H., Dec 23 '16 at 11:46

score 1 · Answer 1 · answered Dec 23 '16 at 11:58

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))

Lisp is seldom written with `camelCase` but `lisp-case`. One of scheme primitives is called `list-ref` that does the same as `nth-item`. Your version is O(n^2) time while the OP had O(n) — Sylwester, Dec 23 '16 at 12:16

score 1 · Answer 2 · answered Dec 23 '16 at 12:08

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.

answered Dec 23 '16 at 12:08

Sylwester

47,942
4
47
79

Input: (diag '((1 2 3) (4 5 6) (7 8 9))) Output: (1 5 9) – K. H. Dec 23 '16 at 12:11
@K.H. I didn't quite get your comment but you have understood my answer. In the recursion when you have `((1 2 3) (4 5 6) (7 8 9))` you need to fetch `1` and recur with `((5 6) (8 9))` – Sylwester Dec 23 '16 at 12:22
Right. The last two lines from the question above will look like this: (cons (caar m) (diag (map cdr (cdr m)))). – K. H. Dec 23 '16 at 12:30
@K.H. Correct. The code you have is elegant. I wouldn't use lists to represent matrices but it works great in this case. – Sylwester Dec 23 '16 at 12:59

score 0 · Answer 3 · answered Dec 26 '16 at 13:12

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))

Find main diagonal in matrix - Scheme

3 Answers3

Linked

Related