Matrix Transpose Common Lisp

Question

Well, i've been told to make a Matrix Transpose function in common lisp. I'm a beginner, so i don't know so much of it.

My Matrix is a list of lists, and i can't use apply, mapcar or similar to solve it, just CONS, CAR and CDR. If not, my solution would be this (I put this solution so someone can use it):

(DEFUN transpose (List)
    (apply #'mapcar #'list List)
)

But I can't use anything of the above.

The function has to be recursive, no loops or similar.

So, the question is, how could this be done?

This is how far i've gone, but it gets me an overflow error. I don't really know how to do it (i could have done it in C++ or Java, but i'm asked to do it in Lisp...)

    (DEFUN transpose (Matrix)
        (COND   ((NULL Matrix) NIL
                ) 
                (T (CONS (CAR(CAR Matrix))(transpose (CONS (CAR(CDR Matrix)) (CDR Matrix))))
                )
        )
    )

Any help would be thanked!

Answer 1

Here is a simple solution that does not use iteration or high-order functions.

(defun cars (matrix)
  "Return a list with all the cars of the lists in matrix"
  (if (null matrix)
      nil
      (cons (car (car matrix)) (cars (cdr matrix)))))

(defun cdrs (matrix)
  "Return a list with all the cdrs of the lists in matrix"
  (if (null matrix)
      nil
      (cons (cdr (car matrix)) (cdrs (cdr matrix)))))

(defun transpose (matrix)
  "Transpose matrix"
  (cond ((null matrix) nil)
        ((null (car matrix)) nil)
        (t (cons (cars matrix) (transpose (cdrs matrix))))))

The function transpose uses two auxiliary functions: cars returns a list with all the first elements of the lists representing the matrix, while cdrs returns a list with all the remaining parts of the lists representing the matrix, so we can use the recursion.

cars works by applying recursively car to all the elements of the lists (that are lists), and return a lista obtained by “consing” them; cdrs works in the same way, this time applying cdr instead of car.