Representing multidimensional arrays as lists of lists ... of array elements is problematic. One problem is that such a value is not of manifest dimensionality. OK so we require that dimensionality be determined by context. The next problem is that n and m should be derivable from an n by m matrix. Yet a 0 by 3 matrix is identical to a 0 by 5 matrix (= ()) but the 3 by 0 matrix is (() () ()). We might go back on the promise but the natural transpose operation would like to turn a 0 by 3 matrix into a 3 by 0 and it can’t find out from its argument the necessary length of the output.
Sometimes it is convenient to let such Scheme values denote arrays, infinite in all dimensions where members beyond some point are all insignificant, such as equal to zero. The routine below transposes an infinite 2D array x but requires a definition of 0, which it must sometimes include in its output, and a test for zero which it must recognize in its input.
(define (trnxx zer zer?) (letrec ((trn (lambda (x) (if (null? x) '() (let m ((u (car x))(v (trn (cdr x)))) (if (null? u) (map (lambda (q) (if (null? q) '() (cons zer q))) v) (if (null? v) (let y ((q u)) (if (null? q) '() (let ((p (y (cdr q)))) (if (and (null? p) (zer? (car q))) '() (cons (if (zer? (car q)) '() (list (car q))) p))))) (cons (cons (car u)(car v)) (m (cdr u)(cdr v)))))))))) trn))(once was)
(define (trnxx zer zer?) (lambda (x) (if (null? x) '() (let ((z ((trnxx zer zer?) (cdr x)))) (let m ((u (car x))(v z)) (if (null? u) (map (lambda (q) (if (null? q) '() (cons zer q))) v) (if (null? v) (let y ((q u)) (if (null? q) '() (let ((p (y (cdr q)))) (if (and (null? p) (zer? (car q))) '() (cons (if (zer? (car q)) '() (list (car q))) p))))) (cons (cons (car u)(car v)) (m (cdr u)(cdr v))))))))))Some examples:
(define tp (trnxx 0 zero?)) (tp '((2 4 5) (2 5 6))) ; => ((2 2) (4 5) (5 6)) (tp '((2 4 5) (2 5 0))) ; => ((2 2) (4 5) (5)) (tp '((2 4 5) (2 5 0) (0 0))) ; => ((2 2) (4 5) (5)) (tp '((2 4 5) (0 0 0) (2 5 0) (0 0))) ; => ((2 0 2) (4 0 5) (5))An accessor for such a matrix, written in the style of “caddar” would always have just two “a”s and would begin “ca”. When such an accessor encounters a non pair it is always '() which indicates that the accessed element should be viewed as 0. A2,3 is extracted as (caddadddr A). Interpreters seldom allow more than 4 a’s and d’s but (caddr (cadddr A)) serves. I think that the above routine always yields the smallest such matrix which means that '(()) will not be found therein, as it is equivalent to the shorter '().
(define (transpose x) (if (null? (car x)) '() (cons (map car x) (transpose (map cdr x)))))