CSE 473 Autumn 1998, Copyright, S. Tanimoto, Univ. of Washington 
Introduction to Artificial Intelligence (Oct 5, 1998)

"List Structure and Recursive Functions"

 

List Structure Representation with Conses


 

CDRing Down a List

;;; FIRST-NUMBER
;;; Return the first number, if any, that occurs in the list LST.
;;; If there aren't any numbers, return NIL.
(defun first-number (lst)
  (if (numberp (car lst)) (car lst))
       (first-number (cdr lst)) ) )
;;; Note: (CDR NIL) = NIL.
 
 


 

Two-Way Recursion: COUNTATOMS

 
 

 
;;; COUNTATOMS
;;; Return the number of atoms in LST.
;;;
(defun countatoms (lst)
  (cond  ((atom lst) 1)
             (t (+ (countatoms (car lst))
                     (countatoms (cdr lst))  )) ) )
 
 

 


 

APPLY and MAPCAR

A functional argument is a function stored as a value.

>  (setq  f   #'+)
#<function ...>

APPLY causes a functional argument to be applied to a list of arguments.

>  (apply  f    '(1 2 3 4 5))
15

>  (defun sqr (x) (*  x  x))
SQR

>  (apply #'sqr  '(7))
49

>  (defun sqr-list (lst)
       (if (null lst) nil
            (cons (sqr (car lst))
                     (sqr-list (cdr lst))  )  )  )

Recursion with APPLY:

>  (defun  apply-to-list  (fn  lst)
       (if (null lst) nil
            (cons (apply fn (list (car lst)))
                     (apply-to-list fn (cdr lst))  )  )  )

>   (apply-to-list #'sqr  '(1 2 3 4 5))
(1 4 9 16 25)

MAPCAR does it for you...
>   (mapcar #'sqr  '(1 2 3 4 5))
(1 4 9 16 25)

 


 

Recursion with MAPCAR

 ;;; PRINT-ALL-SUBLISTS
(defun print-all-sublists  (lst)
  (if (atom lst) nil
      (print lst)
      (mapcar #'print-all-sublists lst)
  )  )

>  (print-all-sublists '(a (b c) d (e (f))) )
(A (B C) D (E (F)))
(B C)
(E (F))
(F)
 
 
 


 

DOLIST and Recursion

(dolist (x '(1 2 3 4 5))
   (print (sqr x)) )
1
4
9
16
25
NIL
 

>  (defun print-all-sublists (lst)
       (if (listp lst)
          (progn
             (print lst)
             (dolist (sublist  lst)
                (print-all-sublists sublist) ) ) ) )
 
 


 
 
 

Exercise: EXIFY

  ;;; EXIFY should take an expression, possibly containing
;;; nested subexpressions, and return an equivalent expression,
;;; except that all symbols have been converted to the symbol X.
 
 

 
 


 
 
 
 
 

Last modified: October 5, 1998

Steve Tanimoto

tanimoto@cs.washington.edu