CS 22
Clab 9: cons cells and deep recursion
I'll start by saying a few words about cons cells, car, cdr, eq?, and
equal?. Then we'll review our flat list remove and subst functions,
noting how we cons up answers while cdring down lists. Finally, we'll
consider deep recursion and look carefully at a deep recrusion version
of remove-first. Then I'll set you loose on the material
below. Solutions to the database stuff from last clab are at the
bottom.
Recall our attempts in clab5 to define: remove-first, remove-all,
and subst over a 'flat' list. Here are solutions.
<![CDATA[
;; remove-first returns a list with the first occurrence of
;; sym removed from the list l:
(define remove-first
(lambda (sym l)
(cond
((null? l) '())
((equal? (car l) sym) (cdr l))
(else (cons (car l) (remove-first sym (cdr l)))))))
;; remove-all returns a list with all occurrences of sym
;; removed from list l:
(define remove-all
(lambda (sym l)
(cond
((null? l) '())
((equal? (car l) sym) (remove-all sym (cdr l)))
(else (cons (car l) (remove-all sym (cdr l)))))))
;; subst returns a list with all occurrences of old
;; replaced with new in list l:
(define subst
(lambda (new old l)
(cond
((null? l) '())
((equal? (car l) old) (cons new (subst new old (cdr l))))
(else (cons (car l) (subst new old (cdr l)))))))
]]>
Note how we are cdring down input lists and consing up solution lists.
Today we would like to do the same functions but over lists that
might contain lists (that might contain lists ...). These are not
flat lists and what we want to do is sometimes called deep-recursion
as opposed to simple recursion.
For example, we would like to define a function remove-first* that
returns a list with the first occurrence of a
symbol removed from an arbitrarily nested list. It should behave as
follows:
<![CDATA[
> names
(mary (jane jill (mary bill) phil) phil ann nathan bill)
>(remove-first* 'phil names)
(mary (jane jill (mary bill)) phil ann nathan bill)
> (remove-first* 'bill names)
(mary (jane jill (mary) phil) phil ann nathan bill)
]]>
Let's look at the following definition together.
<![CDATA[
;; remove-first* returns a list with the first occurrence of
;; sym removed from an arbitrarily nested list l.
(define remove-first*
(lambda (sym l)
(cond
((null? l) '())
((pair? (car l))
(if (equal? (car l) (remove-first* sym (car l)))
(cons (car l) (remove-first* sym (cdr l)))
(cons (remove-first* sym (car l)) (cdr l))))
((eq? (car l) sym) (cdr l))
(else (cons (car l) (remove-first* sym (cdr l)))))))
(define names '(mary (jane jill (mary bill) phil) phil ann nathan bill))
]]>
What difference do you think replacing pair? by list? would make?
Now you write subst* :
<![CDATA[
;; subst* returns a list that substitutes new for old in an arbitrary
;; list, l, of symbols:
(define subst*
(lambda (old new l)
]]>
which should behave like
<![CDATA[
> names
(mary (jane jill (mary bill) phil) phil ann nathan bill)
> (subst* 'bill 'tom names)
(mary (jane jill (mary tom) phil) phil ann nathan tom)
]]>
and remove-all*:
<![CDATA[
;; remove-all* removes all occurrences of sym from an arbitrarily
;; nested list:
(define remove-all*
(lambda (sym l)
]]>
which should behave like
<![CDATA[
> names
(mary (jane jill (mary bill) phil) phil ann nathan bill)
> (remove-all* 'bill names)
(mary (jane jill (mary) phil) phil ann nathan)
> (remove-all* 'mary (remove-all* 'bill names))
((jane jill () phil) phil ann nathan)
]]>
If you have any questions from last clab, or need help finishing up
that material, begin with it and get your questions answered.
ask any questions you may have.
Solutions to database definitions from clab8
<![CDATA[
; rec is assumed to be a record as defined
; above. prop is the name of a property.
; valofpr returns the value of the property
; with property name prop. If rec does not
; have such a property, valofpr returns '().
(define (valofpr rec prop)
(cond
((null? rec) '())
((equal? (caar rec) prop) (cadar rec))
(#t (valofpr (cdr rec) prop))))
; find searches the data base bound to db for
; a record whose property prop has
; value val. If such a record is found,
; find returns the whole record else '().
(define (find db prop val)
(cond
((null? db) '())
((equal? (valofpr (car db) prop) val) (car db))
(#t (find (cdr db) prop val))))
;;; balfromacno searches the database bound to db for a record
;;; with an account number of num. If the search is successful
;;; and if that record has
;;; a property-value sublist with property bal then
;;; the associated value is
;;; returned. If the either the search fails
;;; or there is no property bal,
;;; the empty list is returned.
(define (balfromacno db num)
(valofpr (find db 'acno num) 'bal))
]]>