COMP712 Tutorial #8 ans:
1. Write a function sum-pairs which given a list of numbers will return a list contain the sum of pairs of numbers as shown below:
> (sum-pairs ‘(1 2 3 4))
(3 7)
> (sum-pairs ‘(1 2 3 4 5 6 7))
(3 7 11)
> (sum-pairs ‘(1))
nil
(defun sum-pairs (L)
(cond ((null (cdr L)) nil) ; no second element – finished
(t (cons (+ (car L) (cadr L)) (sum-pairs (cddr L))))))
2. Modify your answer in Q1 to allow sum-pairs take any number of numbers.
> (sum-pairs 1 2 3 4)
(3 7)
(defun sum-pairs2 (& rest L) (sum-pairs L)
Recall that in the lecture, I pointed out you can’t use &rest in a recursive function. You will get an error.
3. Write a function sum-pairs-reverse which given a list of numbers will return a list contain the sum of pairs of numbers (in reverse order) as shown below:
> (sum-pairs-reverse ‘(1 2 3 4))
(7 3)
> (sum-pairs-reverse ‘(1 2 3 4 5 6 7))
(13 9 5)
(defun sum-pairs-reverse (L) (sum-pairs (reverse L)))
4. Write a function My-sum-odd which given a number and a list of numbers will return the sum of all the odd numbers in the list plus the number itself:
> (my-sum-odd 100 ‘(1 2 3 4))
104
> (my-sum-odd 100 ‘())
100
(defun my-sum-odd (n L)
(cond ((null L) n)
((evenp (car L)) (my-sum-odd n (cdr L)))
(t (+ (car L) (my-sum-odd n (cdr L))))))
5. Write a function My-sum-odd2 which given a list of numbers and a number will return the sum of all the odd numbers in the list plus the number itself. If no number is given, it will add 100 by default:
> (my-sum-odd2 ‘(1 2 3 4) 20)
24
> (my-sum-odd2 ‘())
100
(defun my-sum-odd (L &optional (n 100)) ;initialize n to 100
(cond ((null L) n)
((evenp (car L)) (my-sum-odd (cdr L) n))
(t (+ (car L) (my-sum-odd (cdr L) n)))))
6. Using reverse, write a function reverse-less-one which given a list will return the reverse of that list but without its last element:
> (reverse-less-one ‘(1 2 3 4))
(3 2 1)
(defun reverse-less-one (L)
(cdr (reverse L)))
7. The set function, adjoin, adds a new element to the list if it is not there. Write your own adjoin function and called it my-adjoin (hint: use member):
· (my-adjoin ‘a ‘(b c d a))
(b c d a)
· (my-adjoin 2 ‘(3 4 5))
(2 3 4 5)
(defun my-adjoin (n L)
(cond ((member n L) L)
(t (cons n L))))
8. Write a function, even-greater-n, which given a number and a list, return the first even number greater than n:
(defun even-greater-n (n L)
(cond ((null L) nil)
((and (> (car L) n) (evenp (car L))) (car L))
(t (even-greater-n n (cdr L)))))
9. The set function, union, combines two sets into a set. Remember, a set has no repeated element. Write your own union function and called it my-union:
· (my-union ‘(a x z) ‘(b c d a))
(x z b c d a)
· (my-union ‘(a b c) ‘(3 4 5))
(a b c 3 4 5)
(defun my-union (set1 set2)
(cond ((null set1) set2)
((member (car set1) set2) (my-union (cdr set1) set2))
(t (cons (car set1) (my-union (cdr set1) set2)))))
The above is another example of a doubly recursive function and so is Q12.
10. Re-write your answer for Q9, but now use the adjoin function as part of your solution if you haven’t done so already.
(defun my-union (set1 set2)
(cond ((null set1) set2)
(t (my-union (cdr set1) (adjoin (car set1) set2)))))
11. Write a tail-recursive function for Q9.
(defun my-union (set1 set2 &optional (ans set2))
(cond ((null set1) ans)
((member (car set1) set2) (my-union (cdr set1) set2 ans))
(t (my-union (cdr set1) set2 (cons (car set1) ans)))))
Observe that &optional is good, indirectly, for declaring another variable for use in a function!
12. The set function, intersection, returns all common elements. Write your own intersection function and called it my-intersect:
· (my-intersect ‘(a x z) ‘(b c d a))
(a)
· (my-intersect ‘(a b c) ‘(3 4 5))
()
(defun my-intersect (set1 set2)
(cond ((null set1) nil)
((member (car set1) set2)
(cons (car set1) (my-intersect (cdr set1) set2)))
(t (my-intersect (cdr set1) set2))))
13. Write both a recursive and a tail recursive function for factorial.
Recursive:
(defun factorial (N)
(cond ((zerop N) 1)
(t (* N (factorial (1- N))))))
tail-recursive:
(defun factorial (N &optional (ans 1))
(cond ((zerop N) ans)
(t (factorial (1- N) (* ans N)))))
14. Write a function, add-one, which given its arguments will return a list of whereby each number in it has been incremented by 1 according to the following rule. If the first number is odd, increment all remaining odd numbers else increment all remaining even numbers.
· (add-one 1 2 3 4 5)
(4 6)
· (add-one 2)
()
(defun add-one (type &rest L)
(if (oddp type) (inc-odd L) (inc-even L)))
(defun inc-odd (L)
(cond ((null L) nil)
((evenp (car L)) (inc-odd (cdr L)))
(t (cons (1+ (car L)) (inc-odd (cdr L))))))
(defun inc-even (L)
(cond ((null L) nil)
((oddp (car L)) (inc-even (cdr L)))
(t (cons (1+ (car L)) (inc-even (cdr L))))))
15. Write a function list-pair which given its arguments will return a list of lists. Each list is a list of two elements as shown below:
· (list-pair ‘a ‘(b c) ‘d ‘e ‘f 1)
((a (b c)) (d e) (f 1))
· (list-pair ‘a ‘b ‘c ‘d ‘e ‘f 1)
((a b) (c d) (e f))
· (list-pair a)
()
;;remember &rest cannot be used recursively – hence have to
;; call another function
(defun list-pair (&rest L)
(list-pair-aux L))
(defun list-pair-aux (L &optional ans)
(cond ((null L) (reverse ans))
((null (cdr L)) (reverse ans))
(t (list-pair-aux (cddr L) (cons (list (car L) (cadr L)) ans)))))