CS61A Notes 02b – Fake Plastic TreesBox and Pointer DiagramsQUESTIONS: Evaluate the following, and draw a box-and-pointer diagram for each. (Hint: It may beeasier to draw the box-and-pointer diagram first.)1. (cons (cons 1 2) (cons 3 4))+---+---+ +---+---+| | | --+--->| | | | |+-+-+---+ +-+-+-+-+v | |+---+---+ v v| | | | | 3 4+-+-+-+-+| |v v1 22. (cons ‘((1 a) (2 o)) ‘(3 g))+---+---+ +---+---+ +----+---+| | | --+-------->| | | --+---> | | | / |+-+-+---+ +-+-+---+ +-+--+---+| v vv 3 g+---+---+ +---+---+| | | --+--->| | | / |+-+-+---+ +-+-+---+| |v +----------++---+---+ +---+---+ | +---+---+ +---+---+| | | --+->| | | / | +-->| | | --+--->| | | / |+-+-+---+ +-+-+---+ +-+-+---+ +-+-+---+| | | |v v v v1 a 2 oSolutions courtesy of Chung Wu, Justin Chen, Ahmed Owainati3. (list ‘((1 a) (2 o)) ‘(3 g))+---+---+ +---+---+| | | --+-------->| | | / |+-+-+---+ +-+-+---+| | +---+---+ +---+---+v +-------->| | | --+---> | | | / |+---+---+ +---+---+ +-+-+---+ +-+-+---+| | | --+--->| | | / | v v+-+-+---+ +-+-+---+ 3 g| |v +----------++---+---+ +---+---+ | +---+---+ +---+---+| | | --+->| | | / | +-->| | | --+----->| | | / |+-+-+---+ +-+-+---+ +-+-+---+ +-+-+---+| | | |v v v v1 a 2 o4. (append ‘((1 a) (2 o)) ‘(3 g))+---+---+ +---+---+ +---+---+ +---+---+| | | --+--->| | | --+--------->| | | --+------>| | | / |+-+-+---+ +-+-+---+ +-+-+---+ +-+-+---+| | v vv +----------+ 3 g+---+---+ +---+---+ | +---+---+ +---+---+| | | --+->| | | / | +-->| | | --+--->| | | / |+-+-+---+ +-+-+---+ +-+-+---+ +-+-+---+| | | |v v v v1 a 2 o5. (cdr (car (cdr ‘(((1) 3) (4 (5 6))) )))+---+---++ | | / |+-+-+---+v+---+---+ +---+---+| | | --+-->| | | / |+-+-+---+ +-+-+---+v v5 6Solutions courtesy of Chung Wu, Justin Chen, Ahmed Owainati6. (map (lambda (fn) (cons fn (fn 6))) (list square 1+ even?))+---+---+ +---+---+ +---+---+| | | --+----------->| | | --+-------------->| | | / |+-+-+---+ +-+-+---+ +-+-+---+v v v+---+---+ +---+-+ +---+---+ +---+-+ +---+---+ +---+-+| | | --+->| | |/| | | | --+->| | |/| | | | --+-->| | |/|+-+-+---+ +-+-+-+ +-+-+---+ +-+-+-+ +-+-+---+ +-+-+-+v v v v v vsquare 36 1+ 7 even? #t*** Note: square, 1+ and even? are procedures here(Slightly) Harder Lists1. Define a procedure (depth ls) that calculates the maximum depth of sublists in ls. Forexample,(depth ‘(1 2 3 4)) => 1(depth ‘(1 2 (3 4) 5)) => 2(depth ‘(1 2 (3 4 5 (6 7) 8) 9 (10 11) 12)) => 3Remember that there’s a procedure called max that takes in two numbers and returns thegreater of the two.An ATOM is anything that is not a pair.Note that the empty list also falls under this category.(define (depth ls)(if (atom? ls)0(max (1+ (depth (car ls))) (depth (cdr ls)))))2. Define a procedure (remove item ls) that takes in a list and returns a new list withitem removed from ls.If the given list is null, return the empty list.Otherwise, check if the first item in the list is what we wantto remove.Removing an element is accomplished by returning the"processed" rest of the list; in this case the removed versionof the CDR of the list.If we want to keep the first element instead, cons it onto theSolutions courtesy of Chung Wu, Justin Chen, Ahmed Owainatiremoved rest of the list.(define (remove item ls)(cond ((null? ls) nil)((equal? item (car ls))(remove item (cdr ls)))(else (cons (car ls)(remove item (cdr ls))))))3. Define a procedure (unique-elements ls) that takes in a list and returns a new listwithout duplicates. You’ve already done this with remove-dups, and it used to do this:(remove-dups ‘(3 5 6 3 3 5 9 8)) ==> (6 3 5 9 8)where the last occurrence of an element is kept. We’d like to keep the first occurrences:(unique-elements ‘(3 5 6 3 3 5 9 8)) => (3 5 6 9 8)Try doing it without using member?. You might want to use remove above.(define (unique-elements ls)(if (null? ls)'()(cons (car ls) (unique-elements(remove (car ls) (cdr ls))))))4. Define a procedure (count-of item ls) that returns how many times a given itemoccurs in a given list; it could also be in a sublist. So,(count-of ‘a ‘(a b c a a (b d a c (a e) a) b (a))) => 7(define (count-of item ls)(cond ((null? ls) 0)((pair? (car ls))(+ (count-of item (car ls))(count-of item (cdr ls))))((equal? (car ls) item)(1+ (count-of item (cdr ls))))(else (count-of item (cdr ls)))))5. Define a procedure (count-unique ls) which, given a list of elements, returns a list ofpairs whose car is an element and whose cdr is its number of occurrences in the list. Forexample,(count-unique '(a b b b c d d a e e f a a))=> ((a . 4) (b . 3) (c . 1) (d . 2) (e . 2) (f . 1))You might want to use unique-elements and count-of defined above.Solutions courtesy of Chung Wu, Justin Chen, Ahmed Owainati(define (count-unique ls)(map (lambda (x) (cons x (count-of x ls))) (unique-elementsls)))6. Define a procedure (interleave ls1 ls2) that takes in two lists and returns one listwith elements from both lists interleaved. So,(interleave ‘(a b c d) (1 2 3 4 5 6 7)) => (a 1 b 2 c 3 d 4 5 6 7)(define (interleave ls1 ls2)(cond ((null? ls1) ls2)((null? ls2) ls1)(else (cons (car ls1) (interleave ls2 (cdr ls1))))))7. Write a procedure (apply-procs procs args) that takes in a list of single-argumentprocedures and a list of arguments. It then applies each procedure in procs to eachelement in args in order. It returns a list of results. For example,(apply-procs (list square double +1) ‘(1 2 3 4))=> (3 9 19 33)(define (apply-procs procs args)(if (null? procs)args(apply-procs (cdr procs) (map (car procs) args))))Fake Plastic TreesA tree is, abstractly, an acyclic, connected set of nodes (of course, that’s not a very friendly definition).Usually, it is a node that contains two kinds of things – data and children. Data is whateverinformation may be associated with a tree, and children is a set of subtrees with a node as the parent.Concretely, it is often just a list of lists of lists of lists in Scheme, but it’s best NOT to think of trees aslists at all. Trees are trees, lists are lists. They are completely different things, and if you, say, call(car tree) or something like that, that violates the data abstraction. car, cdr, list andappend are for lists, not trees! And don’t bother with box-and-pointer diagrams – they get way toocomplicated for trees. Just let the data abstraction hide the details from you, and trust that theprocedures like make-tree work as intended.Of course, that means we need our own procedures for working with trees analogous to car, cdr,etc. Different representations of trees use
View Full Document
Unlocking...