CS 37

Clab 4: More with lists

From clab03, 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: > a (cat dog amt) > b (horse dog) > (cons a b) ((cat dog amt) horse dog) > (append a b) (cat dog amt horse dog) 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. ;;; 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 run and then evaluate in the interactions window: a b (cons a b) (app a b) Choose language Pretty Big under PLT and press run. Put (require (lib "trace.ss")) in the definitions window and press run.

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: (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
  1. a stopping case-say when lst is empty;
  2. check if el is the first item in lst;
  3. 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 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?.

Now, define and debug the following function. Ask questions if you have them. Make sure your language level is Full Scheme (R5RS).

;; remove-first returns a list with the first occurrence of sym ;; removed from list l: (define remove-first (lambda (sym l) ....

Notice that we cons up a solution after cdring down one of the parameters. This kind of structure is common to many list processing solutions.

Since cs35 is a prereq for this, I assume you are comfortable with the material on pp.42-44. http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.3

On these pages, I will use log n to represent log to the base 2 of n and x^y to represent x raised to the y power.
Recall that log n = k if 2^k = n. So log 16 = 4, log 32 = 5,
log 128 = 7, log 1024 = 10.
Keep in mind that:
100^3 = 1,000,000
log 1,000,000 is about 20
2^100 >> the number of microseconds since the big bang.
This means that if your algorithm has a running time of O(2^n) on inputs of size n, and if want to use it on an input of size 100, you will have to wait a long time to get an answer even if your computer performs a million steps a second. O(n^3) algorithms don't take too long on 100 inputs and O(log n) algorithms are fast on 1,000,000 inputs.

Define and debug the following functions. Ask questions if you have them.
Make sure your language level is Full Scheme (R5RS).
Feel freee to work with your neighbor.

;; remove-all returns a list with all occurrences of sym ;; removed from list l: (define remove-all (lambda (sym l) ..... ;; subst returns a list with all occurrences of old ;; replaced with new in list l: (define subst (lambda (new old l) .... For each of the previous two functions, if you did it so it generated a recursive process, now do it so it generates an iterative process. If you did it so it generated an iterative process, now do it so it generates a recursive process.

Call me over to show what you have got.

That's it for today. If you did it all, you may leave.