From Graham's ANSI Common Lisp: Ch.2: 7-9; Ch.3: 1,3,5; Ch. 4: 1,2,4.
LET, DO, etc.),
define a function that takes a list as an argument and returns true if one
of its elements is a list.
(defun listElem-p (list)
(do ((curList list (cdr curList)))
((or (null curList) (listp (car curList)))
(not (null curList)))))
2.8 Give iterative and recursive definitions of a function that:
(a) takes a positive integer and prints that many dots.
(defun dots-iter (num) (dotimes (x num) (format t ".")) (format t "~%"))
(defun dots-recur (num)
(when (> num 0)
(format t ".")
(dots-recur (1- num))))
(b) takes a list and returns the number of times the symbol a occurs in it.
(defun count-a-iter (list)
(do ((count 0)
(curList list (cdr curList)))
((null curList) count)
(if (eql 'a (car curList))
(setq count (1+ count)))))
(defun count-a-recur (list)
(if (null list)
0
(if (eql (car list) 'a)
(1+ (count-a-recur (cdr list)))
(count-a-recur (cdr list)))))
2.9 A friend is trying to write a function that returns the sum of all the non-nil elements in a list. He has written two versions of this function, and neither of them work. Explain what's wrong with each, and give a correct version:
(a) (defun summit (lst)
(remove nil lst)
(apply #'+ lst))
Remove does not affect lst (i.e., it has no side-effects). Here's a fix:
(defun summit (lst)
(setq lst (remove nil lst))
(apply #'+ lst))
Or, even more simply:
(defun summit (lst)
(apply #'+ (remove nil lst)))
(b) (defun summit (lst)
(let ((x (car lst)))
(if (null x)
(summit (cdr lst))
(+ x (summit (cdr lst))))))
Here, the problem is that there is no base case: it's an
infinite recursion. Here's a fix:
(defun summit (lst)
(if (null lst)
0
(let ((x (car lst)))
(if (null x)
(summit (cdr lst))
(+ x (summit (cdr lst)))))))
3.1 Show the following in box notation:
- (a b (c d))
- (a (b (c (d))))
- (((a b) c) d)
- (a (b . c) . d)
3.3 Define a function that takes a list and returns a list indicating the
number of times each (using eql test) element appears, sorted from most
common element to least common:
> (occurrences '(a b a d a c d c a)) ((A . 4) (C . 2) (D . 2) (B . 1))For this solution, I used a helper function. Here's the whole thing:
(defun occurrences (lst)
(sort (occs lst) #'> :key #'cdr))
(defun occs (lst)
(if (null lst) nil
(let ((lst-shorter (remove (car lst) lst)))
(cons (cons
(car lst)
(- (length lst) (length lst-shorter)))
(occs lst-shorter)))))
3.5 Suppose the function pos+ takes a list of returns alist of each element plus its position:
> (pos+ '( 7 5 1 4)) (7 6 3 7)Define this function using (a) recursion, (b) iteration, (c)
mapcar.
(defun pos+-recur (list &optional (depth 0))
(when list
(cons (+ depth (car list))
(pos+-recur (cdr list) (1+ depth)))))
(defun pos+-recur (list &optional (depth 0))
(when list
(cons (+ depth (car list))
(pos+-recur (cdr list) (1+ depth)))))
(defun pos+-iter (list)
(do ((result nil)
(curList list (cdr curList))
(index 0 (1+ index)))
((null curList) result)
(setq result (append result (list (+ index (car curList)))))))
(defun pos+-mapcar (list)
(let ((index -1))
(mapcar #'(lambda (x) (setq index (1+ index)) (+ index x)) list)))
4.1 Define a function to take a square array and returns the array, rotated 90 degrees clockwise. You'll need array-dimensions (pg. 361).
This is an in-array solution: I don't use another array. It's more complicated
this way, but I thought you might be interested:
;;;Rotates one "ring" of four elements about the center of the array, 90 degrees.
(defun rotate (arr x y)
(let ((tmp (aref arr x y))
(maxIndx (1- (car (array-dimensions arr)))))
(setf (aref arr x y)
(aref arr y (- maxIndx x)))
(setf (aref arr y (- maxIndx x))
(aref arr (- maxIndx x) (- maxIndx y)))
(setf (aref arr (- maxIndx x) (- maxIndx y))
(aref arr (- maxIndx y) x))
(setf (aref arr (- maxIndx y) x) tmp)))
(defun rotateArr (arr)
(let* ((size (car (array-dimensions arr)))
(midIndx (1- (ceiling (/ size 2)))))
(loop for y from 0 to midIndx do
(loop for x from y to midIndx do
(format t "(~d,~d)~%" x y)
(rotate arr x y)))))
4.2 Read the description of reduce on page 368 and 69, then use it to define:
copy-list
reverse (for lists)
(defun my-copy-list (lst)
(reduce #'(lambda (x y)
(format t "~a ~a~%" x y)
(if (listp x)
(append x (list y))
(list x y)))
lst))
(defun my-reverse (lst)
(reduce #'(lambda (x y)
(if (listp x)
(cons y x)
(list y x)))
lst))
4.4 Define a function that takes a BST and returns a list of its elements ordered from greatest to least.
(defun inOrderTraverse (bst)
(and bst
(append
(inOrderTraverse (node-r bst))
(list (node-elt bst))
(inOrderTraverse (node-l bst)))))