Useful things for Assignment 9

Below is the LISP representation of the +animals+ tree for you to work with in writing your 'flatten' function. Also, I include below one implementation of closest-common-ancestor, which should work once you've written 'flatten'. So if you want to, you can put it all together with what we discussed in class to get the 'distance' function. Enjoy! Philip


(defconstant +animals+
  '(top
    (canine
     (domestic-canine
      (big (collie) (doberman))
      (small (chihuahua) (shitzu))
      (hunting (bloodhound) (foxhound)))
     (wild-canine
      (wolf (gray-wolf) (coyote))
      (jackal)
      (fox (red-fox) (kit-fox) (arctic-fox))))
    (feline
     (domestic-feline
      (siamese (blue-point-siamese))
      (manx)
      (angora))
     (wildcat
      (cougar)
      (jaguar)
      (leopard)
      (lion)
      (tiger)))))

(defconstant +animals-isa+ (flatten +animals+)
  "Flat list of ISA relationships for +animals")

(defun parent (node)
  "Returns the parent of node in the +animals+ tree"
  (second (assoc node +animals-isa+)))

(defun is-ancestor (ancestor node)
  "True if ANCESTOR is an ancestor of node in the +animals+ tree"
  (cond ((null node) nil)
	((equal ancestor node) t)
	(t (is-ancestor ancestor (parent node)))))

(defun closest-common-ancestor (node1 node2)
  "Returns the closest common ancestor of node1 and node2 in +animals+"
  (cond ((null node1) nil)
	((is-ancestor node1 node2) node1)
	(t (closest-common-ancestor (parent node1) node2))))