❮ Go Back

CSCI 316: Lisp Assignment 5

This document includes Kong’s official Scheme solutions that were posted after the submission deadline. They have been translated to Common Lisp by an LLM.

Prerequisite: Complete Lisp Assignment 4 first

[Note: If mars fails to operate normally or becomes inaccessible at any time after 6 p.m. on this due date, the submission deadline will not be extended. Try to submit no later than noon that day, and much sooner if you can. Submissions after the due date will be accepted as late submissions until the late-submission deadline; the late-submission deadline will be announced in December. See p. 3 of the 1st-day-announcements document for information regarding late-submission penalties.]

Students were asked some weeks ago to enter source /home/faculty/ykong/316setup at the xxxxx_yyyy316@mars:~$ prompt. You won’t be able to submit this assignment unless / until you have done that!

In this document the term list should be understood to mean proper list.

Scheme solutions to the problems will be provided some days before Exam 1. Students should study the solutions and should be ready to rewrite any solution in Common Lisp if asked to do that on Exam 1.

Assignment

SECTION 1 (Nonrecursive Preliminary Problems)

The three problems in this section (A – C) do not carry direct credit, but are intended to help you solve problems 1 – 3 in Part I of Section 2. Note that there may be questions on exam 1 or on the final exam that are of a similar nature to A – C.

Your solutions to problems A – C must not be recursive. You can test your solutions to these three problems on mars: Functions INDEX, MIN-FIRST, and SSORT with the stated properties are predefined for you when you start Lisp using cl on mars.

A. INDEX

INDEX is a function that is already defined on mars. If N is any positive integer and L is any list, then (INDEX N L) returns the Nth element of L if N does not exceed the length of L; if N exceeds the length of the list L, then (INDEX N L) returns the symbol ERROR. For example: (INDEX 3 '(A S (A S) (A) D)) => (A S) and (INDEX 6 '(A S (A S) (A) D)) => ERROR.

Complete the following definition of a function MY-INDEX without making further calls of INDEX and without calling MY-INDEX recursively, in such a way that if N is any integer greater than 1 and L is any nonempty list then (MY-INDEX N L) is equal to (INDEX N L).

(defun my-index (n L)
  (let ((X (index (- n 1) (cdr L))))
    __))

Note: You should not have to call any functions.

Solution 
X
B. MIN-FIRST

MIN-FIRST is a function that is already defined on mars; if L is any nonempty list of real numbers, then (MIN-FIRST L) is a list whose CAR is the minimum of the numbers in L and whose CDR is the list obtained when the first occurrence of that value is removed from L. Thus (MIN-FIRST L) is “L with the first occurrence of its minimum value moved to the front”. Examples:

(MIN-FIRST '(0 3 1 1 0 3 5)) => (0 3 1 1 0 3 5)
(MIN-FIRST '(4 3 1 1 0 3 5 0 3 0 2)) => (0 4 3 1 1 3 5 0 3 0 2)

Complete the following definition of a function MY-MIN-FIRST without making further calls of MIN-FIRST and without calling MY-MIN-FIRST recursively, in such a way that if L is any list of at least two real numbers then (MY-MIN-FIRST L) is equal to (MIN-FIRST L).

(defun my-min-first (L)
  (let ((X (min-first (cdr L))))
    ___________________________________
    ___________________________________))

There are two cases: (car L) may or may not be ≤ (car X).

Solution 
(cond ((<= (car L) (car X))  L)
      (t  (cons (car X) (cons (car L) (cdr X)))))

* If you have difficulty with these problems, you are encouraged to see me during my office hours. Questions about these problems that are e-mailed to me will not be answered until after the due date.

C. SSORT

SSORT is a function that is already defined on mars; if L is any list of real numbers then (SSORT L) is a list of those numbers in ascending order. Complete the definition below of a function MY-SSORT without making further calls of SSORT and without calling MY-SSORT recursively, in such a way that if L is any nonempty list of real numbers then (MY-SSORT L) is equal to (SSORT L).

(defun my-ssort (L)
  (let* ((L1 (min-first L))
         (X (ssort (cdr L1))))
    __________________________________))
Solution 
(cons (car L1) X)

SECTION 2 (Main Problems)

Your solutions to the following 16 problems will count a total of 1.5% towards your grade if the grade is computed using rule A—the 10 problems in Part I will count 0.75%, and the 6 problems in Part II will also count 0.75%.

It is expected that your solutions to problems 1 – 3 will be based on your solutions to A – C above. [On mars, when you load in your function definitions for problems 1 – 3, you will replace the predefined functions with the same names with your versions of those functions.]

Program in a functional style, without using SETF. Don’t use any features of Lisp other than those introduced in lectures and/or the assigned reading. Follow the indentation and spacing rules in the indentation-&-spacing-rules-for-Lisp-Assignments-2-3-4-5 document on Brightspace.

Use LET / LET* or appropriate helping functions to avoid evaluating computationally expensive expressions more than once. Any helping functions you define for use in your solutions must be defined in the .lsp file that you submit for grading.

When writing a function, decide what you want the valid values for each argument to be. The statement of each problem specifies that certain argument values must be valid. For example, in problem 5 any list of real numbers in ascending order (including the empty list) must be a valid value for each of the arguments; you can choose to make other argument values valid too.

If f computes ( f y …) from ( f ( smaller y ) …) for certain values of y , your base case code needs to ensure this never happens for any value of y that is valid (in the sense of the previous paragraph) for that argument but which satisfies one of the following conditions:

Important Note on Scheme Solutions: The Scheme solutions provided in this document are lambda expressions (anonymous functions) that cannot be invoked as written. A lambda expression by itself is just a data structure that describes a function. To actually run these solutions, you would need to either:

  1. Self-invoke with ((lambda (n l) ...) 3 list) — wrapping the lambda so it becomes the function being called
  2. Pass to higher-order functions like (map (lambda (x) ...) list)
  3. Define a regular named function using (define (index n l) ...), then call (index 3 list)

In their current form in this document, the lambda expressions are just function definitions showing what the logic should be, not executable function calls. Without one of the above approaches, the lambda has no way to be invoked so as to receive its arguments and execute.

PART I

1. INDEX (Recursive)

Define a recursive function INDEX with the properties stated in problem A. Note that the first argument of INDEX may be 1, and that the second argument may be NIL.

Scheme Solution 
(lambda (n l)
  (cond
   ((null? l) 'error)
   ((= n 1) (car l))
   (else (index (- n 1) (cdr l)))))
Common Lisp Solution 
(defun index (n l)
  (cond
   ((endp l) 'error)
   ((= n 1) (car l))
   (t (index (- n 1) (cdr l)))))
2. MIN-FIRST (Recursive)

Define a recursive function MIN-FIRST with the properties stated in problem B. Note that the argument of MIN-FIRST may be a list of length 1.

Scheme Solution 
(lambda (l)
  (cond ((null? (cdr l)) l)
        (else
          (let ((min-first-cdr (min-first (cdr l))))
            (cond
              ((<= (car l) (car min-first-cdr))   l)
              (else
                 (cons (car min-first-cdr) (cons (car l) (cdr min-first-cdr))))))))
Common Lisp Solution 
(defun min-first (l)
  (cond ((endp (cdr l)) l)
        (t
          (let ((min-first-cdr (min-first (cdr l))))
            (cond
              ((<= (car l) (car min-first-cdr))   l)
              (t
                 (cons (car min-first-cdr) (cons (car l) (cdr min-first-cdr)))))))))
3. SSORT (Recursive)

Define a recursive function SSORT with the properties stated in problem C. In the definition of SSORT you may call SSORT itself, MIN-FIRST, CONS, CAR, CDR and ENDP, but you should not call any other function.

Scheme Solution 
(lambda (l)
  (cond
   ((null? l) ())
   (else (let ((l1 (min-first l))) (cons (car l1) (ssort (cdr l1)))))))
Common Lisp Solution 
(defun ssort (l)
  (cond
   ((endp l) nil)
   (t (let ((l1 (min-first l))) (cons (car l1) (ssort (cdr l1)))))))
4. QSORT (Quick Sort)

Use the function PARTITION from Lisp Assignment 4 to complete the following definition of a recursive function QSORT such that if L is a list of real numbers then (QSORT L) is a list of those numbers in ascending order.

(defun qsort (L)
  (if (endp L)
      NIL
      (let ((pL (partition (cdr L) (car L))))
        ...)))
Scheme Solution 
(lambda (l)
  (cond
     ((null? l) ())
     (else
        (let ((pl (partition (cdr l) (car l))))
           (append (qsort (car pl)) (cons (car l) (qsort (cadr pl))))))))
Common Lisp Solution 
(defun qsort (l)
  (cond
     ((endp l) nil)
     (t
        (let ((pl (partition (cdr l) (car l))))
           (append (qsort (car pl)) (cons (car l) (qsort (cadr pl))))))))
5. MERGE-LISTS

Define a Lisp function MERGE-LISTS such that if each of L1 and L2 is a list of real numbers in ascending order then (MERGE-LISTS L1 L2) returns the list of numbers in ascending order that is obtained by merging L1 and L2. Your definition must not call any sorting function.

Examples:

(MERGE-LISTS '(2 4 5 5 7 8 9) '(3 4 6 9 9)) => (2 3 4 4 5 5 6 7 8 9 9 9)
(MERGE-LISTS '(1 2 3) '(4 5 6 7)) => (1 2 3 4 5 6 7)
(MERGE-LISTS '(3 4 5 6 7) '(0 1 2 3)) => (0 1 2 3 3 4 5 6 7)

Hint: Consider the 4 cases L1 = (), L2 = (), (< (car L1) (car L2)), and (>= (car L1) (car L2)).

Scheme Solution 
(lambda (l1 l2)
  (cond
   ((null? l1) l2)
   ((null? l2) l1)
   ((< (car l1) (car l2)) (cons (car l1) (merge-lists (cdr l1) l2)))
   (else (cons (car l2) (merge-lists l1 (cdr l2))))))
Common Lisp Solution 
(defun merge-lists (l1 l2)
  (cond
   ((endp l1) l2)
   ((endp l2) l1)
   ((< (car l1) (car l2)) (cons (car l1) (merge-lists (cdr l1) l2)))
   (t (cons (car l2) (merge-lists l1 (cdr l2))))))
6. MSORT (Merge Sort)

Use the function SPLIT-LIST from Lisp Assignment 4 and MERGE-LISTS to define a recursive Lisp function MSORT such that if L is a list of real numbers then (MSORT L) is a list consisting of the elements of L in ascending order.

In the definition of MSORT you may call SPLIT-LIST, MSORT itself, MERGE-LISTS, CAR, CDR, CADR and ENDP, but you should not call any other function. Be sure to use LET or LET*, so that MSORT only calls SPLIT-LIST once.

Hint: Does a list of length 1 satisfy condition BC-3 (see page 2) for one of your function’s recursive calls?

Scheme Solution 
(lambda (l)
  (cond
   ((null? l) ())
   ((null? (cdr l)) l)
   (else
    (let ((split-l (split-list l)))
      (merge-lists (msort (car split-l)) (msort (cadr split-l)))))))
Common Lisp Solution 
(defun msort (l)
  (cond
   ((endp l) nil)
   ((endp (cdr l)) l)
   (t
    (let ((split-l (split-list l)))
      (merge-lists (msort (car split-l)) (msort (cadr split-l)))))))
7. REMOVE-ADJ-DUPL

Do exercise 10.4(a) on page 418 of Sethi, but use Common Lisp instead of Scheme. Name your function REMOVE-ADJ-DUPL.

Scheme Solution 
(lambda (l)
  (cond
   ((or (null? l) (null? (cdr l))) l)
   ((equal? (car l) (cadr l)) (cons (car l) (cdr (remove-adj-dupl (cdr l)))))
   (else (cons (car l) (remove-adj-dupl (cdr l))))))
Common Lisp Solution 
(defun remove-adj-dupl (l)
  (cond
   ((or (endp l) (endp (cdr l))) l)
   ((equal (car l) (cadr l)) (cons (car l) (cdr (remove-adj-dupl (cdr l)))))
   (t (cons (car l) (remove-adj-dupl (cdr l))))))

Note for problems 8 and 9: One way to do these two problems is to give definitions of the following form:

(defun function-name (L)
  (cond ((endp L) ... )                                           ; L is ()
        ((or (endp (cdr L)) (not (equal (car L) (cadr L)))) ... ) ; L is (x) or (x y ...)
        ((or (endp (cddr L)) (not (equal (car L) (caddr L)))) ... ); L is (x x) or (x x y ...)
        (t ... )))                                                ; L is (x x x ...)
8. UNREPEATED-ELTS

Assume the argument is a list. Do exercise 10.4(b) on page 418 of Sethi in Common Lisp. Name your function UNREPEATED-ELTS.

Scheme Solution 
(lambda (l)
  (cond
   ((null? l) ())
   ((or (null? (cdr l)) (not (equal? (car l) (cadr l))))
    (cons (car l) (unrepeated-elts (cdr l))))
   ((or (null? (cddr l)) (not (equal? (car l) (caddr l))))
    (unrepeated-elts (cddr l)))
   (else (unrepeated-elts (cdr l)))))
Common Lisp Solution 
(defun unrepeated-elts (l)
  (cond
   ((endp l) nil)
   ((or (endp (cdr l)) (not (equal (car l) (cadr l))))
    (cons (car l) (unrepeated-elts (cdr l))))
   ((or (endp (cddr l)) (not (equal (car l) (caddr l))))
    (unrepeated-elts (cddr l)))
   (t (unrepeated-elts (cdr l)))))
9. REPEATED-ELTS

Assume the argument is a list. Do exercise 10.4(c) on page 418 of Sethi in Common Lisp. Name your function REPEATED-ELTS.

Scheme Solution 
(lambda (l)
  (cond
   ((null? l) ())
   ((or (null? (cdr l)) (not (equal? (car l) (cadr l))))
    (repeated-elts (cdr l)))
   ((or (null? (cddr l)) (not (equal? (car l) (caddr l))))
    (cons (car l) (repeated-elts (cddr l))))
   (else (repeated-elts (cdr l)))))
Common Lisp Solution 
(defun repeated-elts (l)
  (cond
   ((endp l) nil)
   ((or (endp (cdr l)) (not (equal (car l) (cadr l))))
    (repeated-elts (cdr l)))
   ((or (endp (cddr l)) (not (equal (car l) (caddr l))))
    (cons (car l) (repeated-elts (cddr l))))
   (t (repeated-elts (cdr l)))))
10. COUNT-REPETITIONS

Assume the argument is a list. Do exercise 10.4(d) on page 418 of Sethi in Common Lisp. Name your function COUNT-REPETITIONS.

Scheme Solution 
(lambda (l)
  (cond
    ((null? l) ())
    ((null? (cdr l)) (list (cons 1 l)))
    (else
      (let ((count-rep-cdr (count-repetitions (cdr l))))
         (cond
            ((not (equal? (car l) (cadr l)))
               (cons (list 1 (car l)) count-rep-cdr))
            (else
               (cons (list (+ 1 (caar count-rep-cdr)) (car l))
                     (cdr count-rep-cdr))))))))
Common Lisp Solution 
(defun count-repetitions (l)
  (cond
    ((endp l) nil)
    ((endp (cdr l)) (list (cons 1 l)))
    (t
      (let ((count-rep-cdr (count-repetitions (cdr l))))
         (cond
            ((not (equal (car l) (cadr l)))
               (cons (list 1 (car l)) count-rep-cdr))
            (t
               (cons (list (+ 1 (caar count-rep-cdr)) (car l))
                     (cdr count-rep-cdr))))))))

PART II

11. SUBSET

[Exercise 8 on p. 141 of Wilensky] Write a recursive function SUBSET that takes two arguments: a function and a list. SUBSET should apply the function to each element of the list, and return a list of all the elements of the argument list for which the function application returns a true (i.e., non-NIL) value.

Example: (subset #'numberp '(a b 2 c d 3 e f)) => (2 3)

Scheme Solution 
(lambda (f l)
  (cond
   ((null? l) ())
   ((f (car l)) (cons (car l) (subset f (cdr l))))
   (else (subset f (cdr l)))))
Common Lisp Solution 
(defun subset (f l)
  (cond
   ((endp l) nil)
   ((funcall f (car l)) (cons (car l) (subset f (cdr l))))
   (t (subset f (cdr l)))))
12. OUR-SOME and OUR-EVERY

[Exercise 7 on p. 141 of Wilensky] Write (i) a recursive function OUR-SOME and (ii) a recursive function OUR-EVERY each of which takes two arguments: a function and a list.

OUR-SOME should apply the function to successive elements of the list until the function returns a true (i.e., non-NIL) value, at which point it should return the rest of the list (including the element for which the function just returned a true value). If the function returns NIL when applied to each of the arguments, OUR-SOME should return NIL.

OUR-EVERY should apply the function to successive elements of the list until the function returns NIL, at which point it should return NIL. If the function returns a true value when applied to each of the arguments, then OUR-EVERY should return T.

Examples:

(our-some #'numberp '(A B 2 C D)) => (2 C D)
(our-some #'numberp '(A B C D)) => NIL
(our-every #'symbolp '(A B 2 C D)) => NIL
(our-every #'symbolp '(A B C D)) => T

* Note that the built-in Lisp function SOME behaves differently from OUR-SOME in this case: SOME returns the non-NIL value that was just returned by the function.

Scheme Solutions

OUR-SOME:

(lambda (f l)
  (cond ((null? l) #f) ((f (car l)) l) (else (our-some f (cdr l)))))

OUR-EVERY:

(lambda (f l)
  (cond ((null? l) #t) (else (and (f (car l)) (our-every f (cdr l))))))
Common Lisp Solutions

OUR-SOME:

(defun our-some (f l)
  (cond ((endp l) nil) ((funcall f (car l)) l) (t (our-some f (cdr l)))))

OUR-EVERY:

(defun our-every (f l)
  (cond ((endp l) t) (t (and (funcall f (car l)) (our-every f (cdr l))))))
13. QSORT1 and PARTITION1

Modify your solutions to problem 7 of Lisp Assignment 4 and problem 4 above to produce a solution to exercise 10.6b on p. 419 of Sethi. Your sorting function should take as arguments a 2-argument predicate p and a list L, and may assume the predicate p and list L are such that:

  1. For all elements x and y of L, (p x y) is true or false—i.e., no error occurs when (p x y) is evaluated.
  2. Whenever x and y are unequal elements of L, at most one of (p x y) and (p y x) is true.
  3. For all elements x, y, and z of L, if (p x y) is true and (p y z) is true then (p x z) is also true.

The sorted list returned by your function should contain exactly the same elements as L, and must satisfy the following condition: Writing si to denote the ith element of the sorted list, we have that (p sk sj) is false whenever the elements sj and sk are unequal and j < k (i.e., sk appears after sj in the sorted list). You can easily verify that the sorted lists in the three examples below satisfy this condition.

Your sorting function and the partition function it uses should be named QSORT1 and PARTITION1.

Examples:

(QSORT1 #'> '(2 8 5 1 5 7 3)) => (8 7 5 5 3 2 1)
(QSORT1 #'< '(2 8 5 1 5 7 3)) => (1 2 3 5 5 7 8)
(QSORT1 (LAMBDA (L1 L2) (< (LENGTH L1) (LENGTH L2)))
        '((X) (A D X E G) (1 2 Q R) NIL (S D F)))
  => (NIL (X) (S D F) (1 2 Q R) (A D X E G))
Scheme Solutions

PARTITION1:

(lambda (l pivot p)
  (cond
     ((null? l) '(() ()))
     (else
        (let ((pcl (partition1 (cdr l) pivot p)))
           (cond
              ((p (car l) pivot)
                 (list (cons (car l) (car pcl)) (cadr pcl)))
              (else
                 (list (car pcl) (cons (car l) (cadr pcl))))))))

QSORT1:

(lambda (p l)
  (cond
     ((null? l) ())
     (else
        (let ((pl (partition1 (cdr l) (car l) p)))
           (append (qsort1 p (car pl))
                   (cons (car l) (qsort1 p (cadr pl))))))))
Common Lisp Solutions

PARTITION1:

(defun partition1 (l pivot p)
  (cond
     ((endp l) (list nil nil))
     (t
        (let ((pcl (partition1 (cdr l) pivot p)))
           (cond
              ((funcall p (car l) pivot)
                 (list (cons (car l) (car pcl)) (cadr pcl)))
              (t
                 (list (car pcl) (cons (car l) (cadr pcl))))))))

QSORT1:

(defun qsort1 (p l)
  (cond
     ((endp l) nil)
     (t
        (let ((pl (partition1 (cdr l) (car l) p)))
           (append (qsort1 p (car pl))
                   (cons (car l) (qsort1 p (cadr pl))))))))
14. FOO

Do exercise 10.12a on p. 420 of Sethi in Common Lisp.

Example:

(FOO #'– '(1 2 3 4 5))
  => ((–1 2 3 4 5) (1 –2 3 4 5) (1 2 –3 4 5) (1 2 3 –4 5) (1 2 3 4 –5))
Scheme Solution 
(lambda (f l)
  (cond
    ((null? l) ())
    (else
       (cons
          (cons (f (car l)) (cdr l))
          (map (lambda (lst) (cons (car l) lst)) (foo f (cdr l)))))))
Common Lisp Solution 
(defun foo (f l)
  (cond
    ((endp l) nil)
    (t
       (cons
          (cons (funcall f (car l)) (cdr l))
          (mapcar (lambda (lst) (cons (car l) lst)) (foo f (cdr l)))))))
Common Lisp Solution 
(defun foo (f l)
  (cond
    ((endp l) nil)
    (t
       (cons
          (cons (funcall f (car l)) (cdr l))
          (mapcar (lambda (lst) (cons (car l) lst)) (foo f (cdr l)))))))
15. Tail Recursion

First, re-read section 8.16 (Advantages of Tail Recursion) on pp. 279–281 of Touretzky. Then solve the following problems.

15(a). TR-ADD, TR-MUL, and TR-FAC

Do exercise 10.5 on p. 419 of Sethi in Common Lisp. Name your functions TR-ADD, TR-MUL and TR-FAC.

Examples:

(TR-ADD '(1 2 3 4 5) 0) => 15
(TR-MUL '(1 2 3 4 5) 1) => 120
(TR-FAC 5 1) => 120

Note: Your definitions of TR-ADD, TR-MUL, and TR-FAC must be tail recursive.

Scheme Solutions

TR-FAC:

(lambda (n res) (cond ((zero? n) res)
                      (else (tr-fac (- n 1) (* n res)))))

TR-ADD:

(lambda (l res) (cond ((null? l) res)
                      (else (tr-add (cdr l) (+ (car l) res)))))

TR-MUL:

(lambda (l res) (cond ((null? l) res)
                      (else (tr-mul (cdr l) (* (car l) res)))))
15(b). SLOW-PRIMEP

Wilson’s Theorem in number theory states that an integer n > 1 is prime if and only if (n – 1)! mod n = n – 1. Use this theorem and TR-FAC to write a predicate SLOW-PRIMEP such that if n > 1 is an integer then (SLOW-PRIMEP n) returns T or NIL according to whether or not n is prime. (You may of course use the built-in function MOD.)

Test your predicate SLOW-PRIMEP by using it to find the least prime number greater than 20,000.

Important: To prevent stack overflow, enter (compile 'tr-fac) at clisp’s > prompt before calling SLOW-PRIMEP with large arguments.

Scheme Solution 
(lambda (n) (= (modulo (tr-fac (- n 1) 1) n) (- n 1)))
Common Lisp Solution 
(defun slow-primep (n) (= (mod (tr-fac (- n 1) 1) n) (- n 1)))
16. TRANSPOSE1, TRANSPOSE2, and TRANSPOSE3

[Based on exercise 8 on p. 111 of Wilensky] A matrix can be represented as a nonempty list of nonempty lists in which the ith element of the jth list is the element in the ith column and jth row of the matrix. For example, ((A B) (C D)) would represent a 2 × 2 matrix whose first row contains the elements A and B, and whose second row contains the elements C and D.

Write three functions TRANSPOSE1, TRANSPOSE2, and TRANSPOSE3, each of which takes a single argument M; if M is a nonempty list of nonempty lists which represents a matrix in the above-mentioned way, then each of the three functions should return the list of lists which represents the transpose of that matrix. The three functions should work as follows:

16(a). TRANSPOSE1

(transpose1 M) computes its result from (transpose1 (cdr M)) and (car M) using mapcar #'cons.

Hint: Take the set of valid values of M to be the set of lists of one or more nonempty lists that all have the same length. Then the BC-2 base case is (null (cdr M)), when the result to be returned is (mapcar #'list (car M)).

Scheme Solution 
(lambda (m)
  (cond ((null? (cdr m)) (map list (car m)))
        (else (map cons (car m) (transpose1 (cdr m))))))
Common Lisp Solution 
(defun transpose1 (m)
  (cond ((endp (cdr m)) (mapcar #'list (car m)))
        (t (mapcar #'cons (car m) (transpose1 (cdr m))))))
16(b). TRANSPOSE2

(transpose2 M) computes its result from (transpose2 (mapcar #'cdr M)) and (mapcar #'car M).

Hint: Again, take the set of valid values of M to be the set of lists of one or more nonempty lists that all have the same length. This time, the BC-2 base case is (null (cdar M)), when the result is (list (mapcar #'car M)).

Scheme Solution 
(lambda (m)
  (cond ((null? (cdar m)) (list (map car m)))
        (else (cons (map car m) (transpose2 (map cdr m))))))
Common Lisp Solution 
(defun transpose2 (m)
  (cond ((endp (cdar m)) (list (mapcar #'car m)))
        (t (cons (mapcar #'car m) (transpose2 (mapcar #'cdr m))))))
16(c). TRANSPOSE3

(transpose3 M) obtains its result as follows: (apply #'mapcar (cons #'??? M)) or, equivalently, (apply #'mapcar #'??? M), where ??? is the name of an appropriate function.

Scheme Solution 
(lambda (m) (apply map list m))
Common Lisp Solution 
(defun transpose3 (m) (apply #'mapcar #'list m))

Example (here n may be 1, 2 or 3):

(TRANSPOSEn '((1 2 3 4) (5 6 7 8) (9 10 11 12)))
  => ((1 5 9) (2 6 10) (3 7 11) (4 8 12))

Submission Instructions

See submission-instructions.md for general submission guidelines that apply to all Lisp assignments.

Assignment-Specific Notes

In this document the term list should be understood to mean proper list.