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:

 

Nick Levine
                                                                               last modified 2000-11-24
                                                         Copyright (C) Nick Levine 1999. All rights reserved.
$Id: //info.ravenbrook.com/user/ndl/lisp/declarative/lectures/solutions/solutions-7.html#2 $