CS 22
Clab 4: Lists
In order to focus on procedural abstraction, your authors work only
with numbers in chapter 1. I want to be able to talk about some other
applications and therefore want to introduce the built-in data
structure, list, now. So... Please skim over the following material
from online help: the first 3 screens worth of section 6.3.2 under
R5RS (get by searching for car then click on (car pair) then scroll to
top of page), then read about quote, cons, car, cdr, list, equal?, null?
in R5RS. Don't worry if you do not understand everything. If
you happen to see set-car! or set-cdr!, turn away fast! These are
examples of GROSS-LISP and we are trying to work in almost-Pure-Lisp
for the time being . Define some lists and try applying these
functions. I'll say a few words in class about lists.
Change your language level to Full Scheme.
Now try evaluating each of the following. Make sure you understand
the result you get. Ask questions if you have them.
<![CDATA[
a
'a
(define a '(cat dog amt))
a
'a
(car a)
(cdr a)
(cons 'horse a)
a
(define b '(horse dog))
a
b
(cons a b)
(car (cdr a))
(define c '(dog horse))
(define d '(horse dog))
a
b
c
d
(equal? a b)
(equal? b d)
(equal? c d) ;;; note that order counts in
;;; list equality.
(eq? b d) ;;; note eq? is different than equal? For now use equal?
(cdr (cdr d))
(cddr d) ;;; short hand for (cdr (cdr d))
(cons 'fun '())
(null? (cdr d))
(null? (cddr d))
]]>
Note that when we cons'd two lists, the first list became one of
the elements of the result instead of the elements of the first list
becoming elements of the result. Frequently, we want the latter
result. In fact, there is a built-in function to achieve that called
append. Compare:
<![CDATA[
> a
(cat dog amt)
> b
(horse dog)
> (cons a b)
((cat dog amt) horse dog)
> (append a b)
(cat dog amt horse dog)
]]>
But in order to understand this better, we will write our
own version of append calling it app so we don't redefine the
built-in append. Put the list definitions of a and b and the following
definition of app in you definitions window.
<![CDATA[
;;; app assumes that both arguments x and y are lists. The result is a new
;;; list consisting of the elements of x followed by the elements of y.
(define (app x y)
(cond
((null? x) y) ;;; if x is empty, return y
(else (cons (car x) (app (cdr x) y))) ;;;otherwise,
;;; return the first element of x
;;; cons'd to the result of app applied to
;;; the rest of x and y
)
)
]]>
Hit execute and then evaluate in the interactions window:
<![CDATA[
a
b
(cons a b)
(app a b)
]]>
Put (require-library "trace.ss") in the definitions window and press execute.
Now put trace on for car, cdr, cons, and app and evaluate
(app a b) making sure
you understand the output of the trace. Ask questions if you have
them.
Now it is time for you to work.
Define a procedure memb? that has the
following specification:
<![CDATA[
(define (memb? el lst) ;; returns #t if el is an element of list lst
.... ;;; returns #f otherwise. Assume lst is a list.
]]>
You can define a recursive procedure to do this using only cond,
null?, equal?, car, and cdr. The idea is to have
- a stopping
case-say when lst is empty;
- check if el is the first item in lst;
- if not, check recursively el is in the rest of the list.
Remember to determine if cat is an element of the predefined
list a, you should evaluate
(memb? 'cat a).
Call me over to check you off when you have debugged your procedure.
Reintroduce yourself to me and show me a demo of what you have.
If I am too busy, just go on and try to catch me sometime to show off
your memb?.
If you have time, define and debug the following function.
Ask questions if you have them.
Make sure your language level is Full Scheme.
<![CDATA[
;; remove-first returns a list with the first occurrence of sym
;; removed from list l:
(define remove-first
(lambda (sym l) ....
]]>