Transpose a matrix in racket (list of lists

Question

I got a list of lists in racket and have to transpose them.

(: transpose ((list-of(list-of %a)) -> (list-of (list-of %a))))

(check-expect (transpose (list (list 1 2 3)
                               (list 4 5 6)))
              (list (list 1 4)
                    (list 2 5)
                    (list 3 6)))

(define transpose
  (lambda (xs)
    (cond
      ((empty? xs)empty)
      ((pair? xs)(make-pair  (make-pair (first(first xs))  (make-pair (first(first(rest xs)))empty)) (transpose (rest(rest xs))))))))

That's my code at the moment. I think the problem is in the recursive call (correct me if I'm wrong please).

The actual outcome is (list (list 1 4)). The rest seems kinda ignored.

It would really help me, if somebody knows the problem, or has a tip.

Answer 1

The simplest definition of transpose is:

(define (transpose xss)
  (apply map list xss))

Why does it work?

  (apply map list '((a b) (d e))
= (apply map List '((a b) (d e))    ; use List rather than list
= (map List '(a b) '(d e))
= (list (List 'a 'd) (List 'b e))
= '((a d) (b e))

Here List is spelled with capital letters only to show which list was given by the user and which was produced by map.

Here is a less "clever" solution. It uses that the first column of a matrix becomes the first row in the transposed matrix.

(define transpose
  (lambda (xss)
    (cond
      [(empty? xss)         empty]
      [(empty? (first xss)) empty]
      [else                 (define first-column   (map first xss))
                            (define other-columns  (map rest  xss))
                            (cons first-column
                                  (transpose other-columns))])))

Answer 2

(define (transpose xss)
  (apply map list xss))

If you are, like me, new to Scheme, you'll wonder how the apply map list trick works. It all boils down to understanding apply and map.

First, apply does its job. It takes a function, some fixed arguments and a list of arguments. It calls the function with the fixed arguments followed by the flattenned list arguments. So:

(apply map list '((1 2) (3 4)))
                ^^^^^^^^^^^^^^-- list of arguments
           ^^^^ ---------------- a fixed argument
       ^^^ --------------------- function

evaluates to:

(map list '(1 2) '(3 4))

Note how the list of lists is turned into two lists.

Now map accepts an N-argument function and N lists of equal length. Then it returns a list, where each element is an application of the function. For example

(map + '(1 2) '(3 4))

evaluates to:

(list (+ 1 3) (+ 2 4))

In the transpose trick the function is simply list, so:

(map list '(1 2) '(3 4))

evaluates to:

(list (list 1 3) (list 2 4))

where the first list constructs a list because map always returns a list and the other two are invocations of the passed list function.

Answer 3

(define (tr ls)
  (if (empty? (car ls)) empty
 (if (null? ls) empty
     (cons (map car ls) (tr (map cdr ls))))))

Answer 4

for/list can be used sequentially to create a list of lists with transposed items:

(define (transpose_ lol)                    ; lol is list of lists
  (for/list ((i (length (list-ref lol 0)))) ; loop for length of first inner list
    (for/list ((il lol))                    ; for each inner list (il)
      (list-ref il i))))                    ; get its item

Testing:

(transpose_ (list (list 1 2 3)
                  (list 4 5 6)))

Output:

'((1 4) (2 5) (3 6))