CSCI 316: Lisp Assignment 4

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.

Due Date: Thursday, October 30

Prerequisite: Complete Lisp Assignment 3 first

Important: 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 on the due date, and much sooner if possible. To give yourself more time to do Lisp Assignment 5 and related reading assignments, I strongly recommend that you complete this assignment well before the due date.

Submissions after the due date will be accepted as late submissions until a late-submission deadline in December that will be announced later. See p. 3 of the 1st-day announcements document for information on late-submission penalties.

Important: 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 and until you have done that!

Collaboration: You may work with up to two other students on these problems. However, as stated on page 2 of the 1st-day announcements document, each student working with a partner must write up their submission independently in their own file; no two students are to submit copies of the same file.

Coding Requirements:

• Program in a functional style without using SETF
• Do not 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

Important Notes About Problem Specifications

In these problems, the behavior of the functions you are asked to complete or write is specified only when the arguments have certain explicitly stated properties. For example:

• In problem A the behavior of MY-SUM is specified only if its argument is a nonempty list of numbers
• In problem 1 the behavior of SUM is specified only if its argument is a (possibly empty) list of numbers

When functions’ arguments do not have the stated properties (e.g., if the argument of MY-SUM is NIL, or if an argument of the function SET-UNION of problem 10 is a list in which some element occurs more than once), the functions’ behavior is unspecified: Your functions are allowed to return any result or to produce an evaluation error in such cases!

Debugging Note: When evaluation of a function call has produced an infinite loop, you can often abort execution by typing Ctrl-C. At a Break …> error prompt, typing backtrace will print, in reverse order, the sequence of all function calls that are in progress.

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

Section 1: Nonrecursive Preliminary Problems

The 7 problems in this section (A – G) do not carry direct credit, but are intended to help you solve problems 1 – 7 in Section 2. There may be exam questions of a similar nature to A – G.

Important: Your solutions to problems A – G must not be recursive. You can test your solutions to these problems on mars:

• Functions SUM, NEG-NUMS, INC-LIST-2, INSERT, ISORT, SPLIT-LIST, and PARTITION with the properties stated in A – G are predefined when you start clisp using cl on mars.
• When a function has 2 cases, test your code in both cases!

A. MY-SUM Function

SUM is a function that is already defined on mars; if L is any list of numbers, then (SUM L) returns the sum of the elements of L. Thus (SUM ()) returns 0.

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

(defun my-sum (L)
  (let ((X (sum (cdr L))))
    __________________________________))

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

Solution

(+ (car L) X)

B. MY-NEG-NUMS Function

NEG-NUMS is a function that is already defined on mars; if L is any list of real numbers, then (NEG-NUMS L) returns a new list that consists of the negative elements of L.

Example:

(NEG-NUMS '(-1 0 -8 2 0 8 -1 -8 2 8 4 -3 0)) => (-1 -8 -1 -8 -3)

Complete the following definition of a function MY-NEG-NUMS without making further calls of NEG-NUMS and without calling MY-NEG-NUMS recursively, in such a way that if L is any nonempty list of numbers then (MY-NEG-NUMS L) is equal to (NEG-NUMS L).

(defun my-neg-nums (L)
  (let ((X (neg-nums (cdr L))))
    ______________________________________
    ____________))

Note: There are two cases: (car L) may or may not be negative.

Solution

(cond ((minusp (car L))  (cons (car L) X))
      (t  X))

C. MY-INC-LIST-2 Function

INC-LIST-2 is a function that is already defined on mars; if L is any list of numbers and N is a number, then (INC-LIST-2 L N) returns a list of the same length as L in which each element is equal to (N + the corresponding element of L).

Examples:

(INC-LIST-2 () 5) => NIL
(INC-LIST-2 '(3 2.1 1 7.9) 5) => (8 7.1 6 12.9)

Complete the following definition of a function MY-INC-LIST-2 without making further calls of INC-LIST-2 and without calling MY-INC-LIST-2 recursively, in such a way that if L is any nonempty list of numbers and N is any number then (MY-INC-LIST-2 L N) is equal to (INC-LIST-2 L N).

(defun my-inc-list-2 (L n)
  (let ((X (inc-list-2 (cdr L) n)))
    __))

Solution

(cons (+ n (car L)) X)

D. MY-INSERT Function

INSERT is a function that is already defined on mars; if N is any real number and L is any list of real numbers in ascending order, then (INSERT N L) returns a list of numbers in ascending order obtained by inserting N in an appropriate position in L.

Examples:

(INSERT 8 ()) => (8)
(INSERT 4 '(0 0 1 2 4)) => (0 0 1 2 4 4)
(INSERT 4 '(0 0 1 3 3 7 8 8)) => (0 0 1 3 3 4 7 8 8)

Complete the following definition of a function MY-INSERT without making further calls of INSERT and without calling MY-INSERT recursively, in such a way that if N is any real number and L is any nonempty list of real numbers in ascending order then (MY-INSERT N L) is equal to (INSERT N L).

(defun my-insert (n L)
  (let ((X (insert n (cdr L))))
    __________________________________
    __________________________________))

Note: There are two cases: N may or may not be ≤ (car L). In the former case you do not need to use X, so if you move that case outside the LET the function will be more efficient.

Solution

(cond ((<= n (car L))  (cons n L))
      (t  (cons (car L) X)))

E. MY-ISORT Function

ISORT is a function that is already defined on mars; if L is any list of real numbers, then (ISORT L) is a list consisting of the elements of L in ascending order.

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

(defun my-isort (L)
  (let ((X (isort (cdr L))))
    __))

Hint: You should not have to call any function other than INSERT and CAR.

Solution

(insert (car L) X)

F. MY-SPLIT-LIST Function

IMPORTANT: If you have not yet done problem 8 in part F of Lisp Assignment 1, do that problem before you work on this problem!

SPLIT-LIST is a function that is already defined on mars; if L is any list, then (SPLIT-LIST L) returns a list of two lists, in which the first list consists of the 1st, 3rd, 5th, … elements of L, and the second list consists of the 2nd, 4th, 6th, … elements of L.

Examples:

(SPLIT-LIST ()) => (NIL NIL)
(SPLIT-LIST '(A B C D 1 2 3 4 5)) => ((A C 1 3 5) (B D 2 4))
(SPLIT-LIST '(B C D 1 2 3 4 5)) => ((B D 2 4) (C 1 3 5))
(SPLIT-LIST '(A)) => ((A) NIL)

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

(defun my-split-list (L)
  (let ((X (split-list (cdr L))))
    __________________________________))

Solution

(list (cons (car L) (cadr X))
      (car X))

G. MY-PARTITION Function

PARTITION is a function that is already defined on mars; if L is a list of real numbers and P is a real number, then (PARTITION L P) returns a list whose CAR is a list of the elements of L that are strictly less than P, and whose CADR is a list of the other elements of L. Each element of L must appear in the CAR or CADR of (PARTITION L P), and should appear there just as many times as in L.

Examples:

(PARTITION '(7 5 3 2 1 5) 1) => (NIL (7 5 3 2 1 5))
(PARTITION '(4 0 5 3 1 2 4 1 4) 4) => ((0 3 1 2 1) (4 5 4 4))
(PARTITION () 9) => (NIL NIL)

Complete the following definition of a function MY-PARTITION without making further calls of PARTITION and without calling MY-PARTITION recursively, in such a way that if L is any nonempty list of real numbers and P is a real number then (MY-PARTITION L P) is equal to (PARTITION L P).

(defun my-partition (L p)
  (let ((X (partition (cdr L) p)))
    ___________________________________________
    __________________________________))

Note: There are two cases: (car L) may or may not be less than P.

Solution

Scheme:

(define (my-partition L p)
  (let ((X (partition (cdr L) p)))
    (if (< (car L) p)
        (list (cons (car L) (car X)) (cadr X))
        (list (car X) (cons (car L) (cadr X))))))

Common Lisp:

(cond ((< (car L) p) (list (cons (car L) (car X)) (cadr X)))
      (t  (list (car X) (cons (car L) (cadr X)))))

Section 2: Main Problems

Your solutions to problems 1 – 13 will count a total of 1.5% towards your grade if it is computed using rule A.

Helpful Note: A working solution to each of problems 1 – 7 can be obtained from a solution to the corresponding one of problems A – G by changing the name of the function MY-FUNC to FUNC and adding appropriate base case code, without changing the LET block. The resulting definition of FUNC will be correct because it will have the following property: In all non-base cases where FUNC’s recursive call returns the correct result, FUNC returns the same result as MY-FUNC. Assuming your definition of MY-FUNC is correct, this property implies that in non-base cases FUNC returns the correct result whenever FUNC’s recursive call returns the correct result, which in turn implies FUNC never returns an incorrect result if your base case code is correct.

If you solve a problem this way then any cases that do not need to use the LET’s local variable should be moved out of the LET, and the LET should be eliminated if the value of its local variable is never used more than once.

Important Notes:

1. When you start Clisp using cl on mars and LOAD a function definition for any of problems 1–7, your function will replace the predefined function with the same name, and Clisp will issue a WARNING that it is redefining the predefined function. Such WARNINGs should be ignored! However, if the function you write for one of problems 1 – 7 is wrong, then after you LOAD that definition on mars, the MY-* function you wrote for the corresponding one of problems A – G may stop working (because it calls the function you redefined).

2. You may use ENDP or NULL to test whether a list is empty. Recall that (ENDP L) returns the same result as (NULL L) if the value of L is a list. But evaluation of (ENDP L) produces an error if the value of L is an atom other than NIL.

Problem 1: SUM

Define a recursive function SUM with the properties stated in problem A. Note that whereas NIL is not a valid argument of MY-SUM, NIL is a valid argument of SUM.

Scheme Solution

(define (sum l)
  (cond ((null? l) 0)
        (else (+ (car l) (sum (cdr l))))))

Common Lisp Solution

(defun sum (l)
  (cond ((null l) 0)
        (t (+ (car l) (sum (cdr l))))))

Problem 2: NEG-NUMS

Define a recursive function NEG-NUMS with the properties stated in problem B. Note that NIL is a valid argument of NEG-NUMS.

Scheme Solution

(define (neg-nums l)
  (cond ((null? l) '())
        ((< (car l) 0)
         (cons (car l) (neg-nums (cdr l))))
        (else
         (neg-nums (cdr l)))))

Common Lisp Solution

(defun neg-nums (l)
  (cond ((null l) nil)
        ((< (car l) 0)
         (cons (car l) (neg-nums (cdr l))))
        (t
         (neg-nums (cdr l)))))

Problem 3: INC-LIST-2

Define a recursive function INC-LIST-2 with the properties stated in problem C. Note that the first argument of INC-LIST-2 may be NIL.

Scheme Solution

(define (inc-list-2 l n)
  (cond ((null? l) '())
        (else
         (cons (+ n (car l))
               (inc-list-2 (cdr l) n)))))

Common Lisp Solution

(defun inc-list-2 (l n)
  (cond ((null l) nil)
        (t
         (cons (+ n (car l))
               (inc-list-2 (cdr l) n)))))

Problem 4: INSERT

Define a recursive function INSERT with the properties stated in problem D. Note that the second argument of INSERT may be NIL.

Scheme Solution

(define (insert n l)
  (cond ((null? l) (list n))
        ((<= n (car l))
         (cons n l))
        (else
         (cons (car l) (insert n (cdr l))))))

Common Lisp Solution

(defun insert (n l)
  (cond ((null l) (list n))
        ((<= n (car l))
         (cons n l))
        (t
         (cons (car l) (insert n (cdr l))))))

Problem 5: ISORT

Define a recursive function ISORT with the properties stated in problem E.

Hint: In your definition of ISORT you should not have to call any function other than ISORT itself, INSERT, CAR, CDR, and ENDP or NULL. (An IF or COND form is not considered to be a function call, and may be used.)

Scheme Solution

(define (isort l)
  (cond ((null? l) '())
        (else
         (insert (car l) (isort (cdr l))))))

Common Lisp Solution

(defun isort (l)
  (cond ((null l) nil)
        (t
         (insert (car l) (isort (cdr l))))))

Problem 6: SPLIT-LIST

Define a recursive function SPLIT-LIST with the properties stated in problem F.

Scheme Solution

(define (split-list l)
  (cond ((null? l) '(() ()))
        (else
         (let ((split-cdr (split-list (cdr l))))
           (list (cons (car l) (cadr split-cdr))
                 (car split-cdr))))))

Common Lisp Solution

(defun split-list (l)
  (cond ((null l) '(nil nil))
        (t
         (let ((split-cdr (split-list (cdr l))))
           (list (cons (car l) (cadr split-cdr))
                 (car split-cdr))))))

Problem 7: PARTITION

Define a recursive function PARTITION with the properties stated in problem G.

Scheme Solution

(define (partition l pivot)
  (cond ((null? l) '(() ()))
        (else
         (let ((pcl (partition (cdr l) pivot)))
           (cond ((< (car l) pivot)
                  (list (cons (car l) (car pcl))
                        (cadr pcl)))
                 (else
                  (list (car pcl)
                        (cons (car l) (cadr pcl)))))))))

Common Lisp Solution

(defun partition (l pivot)
  (cond ((null l) '(nil nil))
        (t
         (let ((pcl (partition (cdr l) pivot)))
           (cond ((< (car l) pivot)
                  (list (cons (car l) (car pcl))
                        (cadr pcl)))
                 (t
                  (list (car pcl)
                        (cons (car l) (cadr pcl)))))))))

Problem 8: POS

Without using MEMBER, complete the following definition of a recursive function POS such that if L is a list and E is an element of L then (POS E L) returns the position of the first occurrence of E in L, but if L is a list and E is not an element of L then (POS E L) returns 0.

Examples:

(POS 5 '(1 2 5 3 5 5 1 5)) => 3
(POS 'A '(3 2 1)) => 0
(POS '(3 B) '(3 B)) => 0
(POS '(A B) '((K) (3 R C) A (A B) (K L L) (A B))) => 4
(POS '(3 B) '((3 B))) => 1

Scheme Solution

(define (pos x l)
  (cond
    ((null? l) 0)
    ((equal? x (car l)) 1)
    (else
     (let ((p (pos x (cdr l))))
       (cond ((zero? p) 0)
             (else (+ 1 p)))))))

Common Lisp Solution

(defun pos (x l)
  (cond
    ((null l) 0)
    ((equal x (car l)) 1)
    (t
     (let ((p (pos x (cdr l))))
       (cond ((zerop p) 0)
             (t (+ 1 p)))))))

Problem 9: SPLIT-NUMS

Define a recursive function SPLIT-NUMS such that if N is a non-negative integer then (SPLIT-NUMS N) returns a list of two lists: The first of the two lists consists of the even integers between 0 and N in descending order, and the other list consists of the odd integers between 0 and N in descending order.

Examples:

(SPLIT-NUMS 0) => ((0) NIL)
(SPLIT-NUMS 7) => ((6 4 2 0) (7 5 3 1))
(SPLIT-NUMS 8) => ((8 6 4 2 0) (7 5 3 1))

Scheme Solution

(define (split-nums n)
  (cond ((zero? n) '((0) ()))
        (else
         (let ((X (split-nums (- n 1))))
           (cond ((even? n)
                  (list (cons n (car X)) (cadr X)))
                 (else
                  (list (car X) (cons n (cadr X)))))))))

Common Lisp Solution

(defun split-nums (n)
  (cond ((zerop n) '((0) nil))
        (t
         (let ((X (split-nums (- n 1))))
           (cond ((evenp n)
                  (list (cons n (car X)) (cadr X)))
                 (t
                  (list (car X) (cons n (cadr X)))))))))

Problems 10–13: Set Operations

Important: In problems 10 – 13 the term set is used to mean a proper list of numbers and/or symbols in which no atom occurs more than once. You may use MEMBER but not the functions UNION, NUNION, REMOVE, DELETE, SET-DIFFERENCE, and SET-EXCLUSIVE-OR.

Problem 10: SET-UNION

Define a recursive function SET-UNION such that if s1 and s2 are sets then (SET-UNION s1 s2) is a set that contains the elements of s1 and the elements of s2, but no other elements. Thus (SET-UNION '(A B C D) '(C E F)) should return a list consisting of the atoms A, B, C, D, E, and F (in any order) in which no atom occurs more than once.

Scheme Solution

(define (set-union s1 s2)
  (cond ((null? s1) s2)
        ((member (car s1) s2)
         (set-union (cdr s1) s2))
        (else
         (cons (car s1) (set-union (cdr s1) s2)))))

Common Lisp Solution

(defun set-union (s1 s2)
  (cond ((null s1) s2)
        ((member (car s1) s2)
         (set-union (cdr s1) s2))
        (t
         (cons (car s1) (set-union (cdr s1) s2)))))

Problem 11: SET-REMOVE

Define a recursive function SET-REMOVE such that if s is a set and x is an atom in s then (SET-REMOVE x s) is a set that consists of all the elements of s except x, but if s is a set and x is an atom which is not in s then (SET-REMOVE x s) returns a set that is equal to s.

Scheme Solution

(define (set-remove x s)
  (cond ((null? s) '())
        ((equal? x (car s)) (cdr s))
        (else
         (cons (car s) (set-remove x (cdr s))))))

Common Lisp Solution

(defun set-remove (x s)
  (cond ((null s) nil)
        ((equal x (car s)) (cdr s))
        (t
         (cons (car s) (set-remove x (cdr s))))))

Problem 12: SET-EXCL-UNION

(Note: You may use the function SET-REMOVE from problem 11.)

Define a recursive function SET-EXCL-UNION such that if s1 and s2 are sets then (SET-EXCL-UNION s1 s2) is a set that contains all those atoms that are elements of exactly one of s1 and s2, but no other atoms. (SET-EXCL-UNION s1 s2) does not contain any atoms that are neither in s1 nor in s2, and also does not contain the atoms that are in both of s1 and s2.

Example:

(SET-EXCL-UNION '(A B C D) '(E C F G A)) => (B D E F G)  ; in any order

Scheme Solution

(define (set-excl-union s1 s2)
  (cond ((null? s1) s2)
        ((member (car s1) s2)
         (set-remove (car s1) (set-excl-union (cdr s1) s2)))
        (else
         (cons (car s1) (set-excl-union (cdr s1) s2)))))

Common Lisp Solution

(defun set-excl-union (s1 s2)
  (cond ((null s1) s2)
        ((member (car s1) s2)
         (set-remove (car s1) (set-excl-union (cdr s1) s2)))
        (t
         (cons (car s1) (set-excl-union (cdr s1) s2)))))

Problem 13: SINGLETONS

(Note: You may use the function SET-REMOVE from problem 11.)

Define a recursive function SINGLETONS such that if e is any list of numbers and/or symbols then (SINGLETONS e) is a set that consists of all the atoms that occur just once in e.

Examples:

(SINGLETONS ()) => NIL
(SINGLETONS '(G A B C B)) => (G A C)
(SINGLETONS '(H G A B C B)) => (H G A C)
(SINGLETONS '(A G A B C B)) => (G C)
(SINGLETONS '(B G A B C B)) => (G A C)

Hint: When e is nonempty, consider the case in which (car e) is a member of (cdr e), and the case in which (car e) is not a member of (cdr e).

Scheme Solution

(define (singletons e)
  (cond ((null? e) '())
        ((member (car e) (cdr e))
         (set-remove (car e) (singletons (cdr e))))
        (else
         (cons (car e) (singletons (cdr e))))))

Common Lisp Solution

(defun singletons (e)
  (cond ((null e) nil)
        ((member (car e) (cdr e))
         (set-remove (car e) (singletons (cdr e))))
        (t
         (cons (car e) (singletons (cdr e))))))

Submission Instructions

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

Assignment-Specific Notes

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