CMSC 671 - Fall '01
LECTURE NOTES FOR 9/6/01
Prof. Marie desJardins


4:00 - 4:45	  Problem solving as search / uninformed search
4:45 - 5:15	  More detailed Lisp example (nested-find-odd)


-- PROBLEM DEFINITION
Given an arbitrary nested list, find and return a list of all
of the odd numbers in the list, in the order they are found
(depth-first!)

-- ODDNESS
First need a function for oddness - luckily, it already exists!
      #'oddp
But it requires an integer, so let's write a new version with
error checking
      (defun my-oddp (n)
	     (and (integerp n) (oddp n)))

-- FINDING THINGS
Let's write a function to recursively look for an odd thing.
We'll worry about returning things properly later.
      (defun my-find (l)
	(cond ((my-oddp l) l)
	      ((listp l) (and (my-find (car l)) (my-find (cdr l))))
	      (t nil)))
"And" short-circuits, so we never look at the rest of the list if
 we fail to find an oddp thing in the first part of the list.

-- LOOKING AT EVERYTHING
      (defun my-find (l)
	(cond ((my-oddp l) l)
	      ((listp l) (progn (my-find (car l)) (my-find (cdr l))))
	      (t nil)))

Now we get an infinite loop because we didn't check for NULL (which is
listp).

-- FIXING THE BUGS
      (defun my-find (l)
	(cond ((null l) nil)
	      ((my-oddp l) l)
	      ((listp l) (progn (my-find (car l)) (my-find (cdr l))))
	      (t nil)))

-- RETURN VALUES
Now let's gather things up properly.
(defun my-find (l)
  (cond ((null l) nil)
	((my-oddp l) (list l))
	((listp l) (append (my-find (car l)) (my-find (cdr l))))
	(t nil)))

-- SPACE EFFICIENCY
We're never going to need the individual return results, so we
can destructively modify them
(defun my-find (l)
  (cond ((null l) nil)
	((my-oddp l) (list l))
	((listp l) (nconc (my-find (car l)) (my-find (cdr l))))
	(t nil)))

-- A CLEVER SOLUTION USING THE LOOP MACRO
Because we're looping over the elements (instead of breaking the
list into car/cdr), we don't need the test for null any more.
(defun my-find (l)
  (cond ((listp l) (loop for x in l do
			 nconc (my-find x)))
	((my-oddp l) (list l))
	(t nil)))

-- YET ANOTHER IMPLEMENTATION, USING MAPCAR
(defun my-find (l)
  (cond ((listp l) (mapcar #'my-find l))
	((my-oddp l) l)
	(t nil)))
This is buggy because the return list is nested

-- SLIGHTLY BETTER
(defun my-find (l)
  (cond ((listp l) (remove-if #'null (mapcar #'my-find l)))
	((my-oddp l) l)
	(t nil)))
At least we got rid of the NULLs

-- BETTER STILL (at least it works!)
(defun my-find (l)
  (cond ((listp l) (apply #'nconc (mapcar #'my-find l)))
	((my-oddp l) (list l))
	(t nil)))

-- EVEN EASIER -- USE MAPCAN!
(defun my-find (l)
  (cond ((listp l) (mapcan #'my-find l))
	((my-oddp l) (list l))
	(t nil)))