Solutions to exercises from "lecture notes 7"

(defun reducing-copy-list (list)
(reduce 'cons list :from-end t :initial-value nil))

(defun reducing-reverse (list)
(reduce (lambda (x y) (cons y x)) list :initial-value nil))

;;;;;;;;;;
#||

(defstruct node
data
child-1
child-2
child-3)

(defun copy-all-nodes (node)
(when node
(make-node :data (node-data node)
:child-1 (copy-all-nodes (node-child-1 node))
:child-2 (copy-all-nodes (node-child-2 node))
:child-3 (copy-all-nodes (node-child-3 node)))))

(defun node-find (data node)
(when node
(or (eql data (node-data node))
(node-find data (node-child-1 node))
(node-find data (node-child-2 node))
(node-find data (node-child-3 node)))))

||#
;;;;;;;;;;;

;; Actually I prefer the following, which does not assume the number
;; of child nodes and produces cleaner code...

(defstruct node
data
children)

(defun copy-all-nodes (node)
(make-node :data (node-data node)
:children (mapcar 'copy-all-nodes (node-children node))))

(defun node-find (data node)
(or (eql data (node-data node))
(dolist (child (node-children node))
(when (node-find data child)
(return t)))))

;;;;;;;;;;;

(defun govt-cons (car cdr)
(cons cdr car))

(defun govt-car (x)
(cdr x))
(defun govt-cdr (x)
(car x))

;; this question is difficult to interpret - I guess it means that the
;; argument to govt-list is a proper list -- otherwise if the argument
;; was already a govt-list we could say (defun govt-list (&rest x) x) ...
(defun govt-list (&rest things)
(in-govt-list things))

(defun in-govt-list (things)
(when things
(govt-cons (car things)
(in-govt-list (cdr things)))))

(defun govt-length (list)
(if list
(1+ (govt-length (govt-cdr list)))
0))

(defun govt-member (thing govt-list)
(when govt-list
(if (eql thing (govt-car govt-list))
govt-list
(govt-member thing (govt-cdr govt-list)))))

;;;;;;;;;;;

;; this looks like a total rewrite to me (sigh)

(defun lottery-distinct ()
(in-lottery-distinct nil 6))

(defun in-lottery-distinct (numbers how-many)
(if (plusp how-many)
(let* ((next (1+ (random 49))))
(if (find next numbers)
(in-lottery-distinct numbers how-many)
(in-lottery-distinct (cons next numbers) (1- how-many))))
(sort numbers '<)))

(defun lottery-distinct-iterative ()
(let* ((numbers nil)
(how-many 6))
(loop (let* ((next (1+ (random 49))))
(unless (find next numbers)
(push next numbers)
(when (zerop (decf how-many))
(return (sort numbers '<))))))))

;;;;;;;;;;;

(defun maximum-with-lambda (numbers)
(let* ((best (first numbers)))
(mapc (lambda (number)
(if (> number best)
(setf best number)))
(rest numbers))
best))

(defun dotty-with-lambda (things)
(mapc (lambda (junk)
(declare (ignore junk))
(format t "."))
things))

;;;;;;;;;;;

;; similar to the govt-cons above

;; probably don't need a my-nil (depends how it's going to be used...)

(defstruct my-cons
car
cdr)

(defun my-first (thing)
(my-cons-car thing))

(defun my-rest (thing)
(my-cons-cdr thing))

(defun my-cons (first rest) ; NB ok to have function name same as structure
(make-my-cons :car first :cdr rest))

(defun my-list (&rest things)
(in-my-list things))
(defun in-my-list (things)
(when things
(make-my-cons :car (first things)
:cdr (in-my-list (rest things)))))

(defun my-length (thing)
(if thing
(1+ (my-length (my-rest thing)))
0))

If you have tried the exercises, looked at the solutions and still do not understand what's going on, I am available for consultation at the times advertised on my office door. Bring your code with you in BOTH the following forms:

• Logbook containing printout (nothing handwritten please)
• file on floppy

Nick Levine