CSC 324, Fall 2005 Tutorial notes for the week of October 17, 2005. 4 topics were covered in tutorial: 1- Assignment 2 2- Quick review of recursive procedures 3- Higher-order procedures (map, apply, reduce) 4- 3 ways to improve efficiency - let for local variable bindings to avoid recomputation - helper procedures to avoid recomputation - accumulators =================================================================== 1. Discussion of A2 =================================================================== 2. Recursive Procedures Practice Problems In all four procedures, e is an atom and lst is a non-nested list. ----------------------------------------------- 2.1 PROBLEM: (member e lst) => returns #t if e is in lst, #f/() otherwise. SOLUTION: (define (member e lst) (cond ((null? lst) #f) ((eq? e (car lst)) #t) (else (member e (cdr lst))) )) OR: (define (member e lst) (and (not (null? lst)) ; the list is not null, and (or (eq? e (car lst)) ; either e is the car of lst, (member e (cdr lst)))) ; or e is in the cdr of lst ) -------------------------------------------------------- 2.2 PROBLEM: (union lst1 lst2) => returns a list consisting of all elements in either lst1 or lst2, with no duplicates. SOLUTION: (define (union lst1 lst2) (cond ((null? lst1) lst2) ((member (car lst1) lst2) (union (cdr lst1) lst2)) (else (cons (car lst1) (union (cdr lst1) lst2))) )) NOTE: - this is just like append, except that you have a condition to decide whether to cons the car of lst1 onto lst2 or not. Given this similarity, an alternative to the above is to append the lists, then remove the duplicates. Unfortunately, it is less efficient because it means traversing the first list (in append) and then traversing the combined list and comparing each element of the combined list to each element of the rest of the list (to remove duplicates). In the above solution, you only traverse the first list comparing each element to each element of the second list, so it's fewer comparisons. On the other hand, if you had already written a remove-duplicates procedure, the alternative solution has the virtue of simplicity. -------------------------------------------------------------- 2.3 (OPTIONAL) PROBLEM: (intersection lst1 lst2) => returns a list consisting of all the elements that are in both lst1 and lst2. SOLUTION: (define (intersection lst1 lst2) (cond ((null? lst1) '()) ((member (car lst1) lst2) (cons (car lst1) (intersection (cdr lst1) lst2))) (else (intersection (cdr lst1) lst2)) )) *NOTE* If you do this one, discuss the differences with union: - different base cases (why?) - "opposite" conditions on cons'ing the car of lst1 ----------------------------------------------------------------- 2.4 EXERCISE TO DO AT HOME (difference lst1 lst2) => returns a list consisting of all elements that are in lst1 and NOT in lst2. ===================================================================== 3. Higher Order Procedures (HOPs) - Practice with map/apply/reduce General things to emphasize: ----------------------------- - breaking the code into small steps and using helper procedures to avoid convoluted code and complex nested conds. - use of higher-order procedures to create simple solutions using procedures they have already written. You have now seen 'map', 'apply', and 'my-reduce' in class. The first two are built-in HOPs; the third is one we defined in class. Here is the code for your reference: ; (my-reduce op lst id) applies the binary operator op to the elements of ; list right-associatively, or returns id (the identity element) if lst ; is empty. ; Pre: op is a binary procedure, lst is a list of valid arguments to op, ; and id is the identity value for op, i.e., (op x id) => x for all x that ; are valid arguments to op. (define my-reduce (lambda (op lst id) (cond ((null? lst) id) (else (op (car lst) (my-reduce op (cdr lst) id))))) E.g.: (my-reduce / '(24 6 2) 1) => 8 The beauty of my-reduce is that it can convert a binary procedure into an n-ary procedure. E.g., "union" takes 2 lists and returns their union, so when we have a list of 2 lists, we can use apply, (apply union '((1 3) (2 3 4)) => (1 2 3 4) BUT (apply union '((1 3) (2 3) (4 5))) produces an error INSTEAD (reduce union '((1 3) (2 3) (4 5)) ()) => (1 2 3 4 5) (Trace reduce, if you're still unclear. (There is a trace in the latest class notes.) Below are some practice problems, using the set procedures we just developed, some of which make use of HOPs. * NOTE: For these, do not worry about efficiency -- the idea is to best make use of procedures they have already written using HOPs. Simplicity is more important here than efficiency (see my solutions). ------------------------------------------------------------------- 3.1 PROBLEM: (intersect-all lst1 lst2) => returns a list of elements that corresponding sublists of lst1 and lst2 have in common, with no duplicates. (lst1 and lst2 are lists of lists, with the same number of sublists.) Example: If l1 is '((1 2 4 5) (2 4 5) (3 8)) l2 is '((1 3 5) (2 5) (1 5 8)) (intersect-all l1 l2) => (1 2 5 8) (Note: order of elements in result doesn't matter. I've listed them in numeric order. That happens to be the order you get with my solution.) SOLUTION: Helper procedure: (define (rm-dups lst) (cond ((null? lst) '()) ((member (car lst) (cdr lst)) (rm-dups (cdr lst))) (else (cons (car lst) (rm-dups (cdr lst)))) )) (define (intersect-all lst1 lst2) (rm-dups (apply append (map intersection lst1 lst2))) ) --------------------------------------------------------------------- 3.2 PROBLEM: (union-all lst1 lst2) => returns a list of elements consisting of the union of corresponding sublists of lst1 and lst2, with no duplicates. (lst1 and lst2 are lists of lists, with the same number of sublists.) Example: If l1 is '((1 2 4 5) (2 4 5) (3 8)) l2 is '((1 3 5) (2 5) (1 5 8)) (union-all l1 l2) => (1 2 3 4 5 8) (Note: order of elements in result doesn't matter -- I've listed them in numeric order, but that is not the order you get with either of my solutions.) SOLUTION: (define (union-all lst1 lst2) (rm-dups (apply append (map union lst1 lst2))) ) **** NOTE: This is exactly like intersection. See if they can think of an alternative way to do this, as: (define (union-all lst1 lst2) (rm-dups (union (apply append lst1) (apply append lst2))) ) **** There's even a way that uses union twice! (define (union-all lst1 lst2) (reduce union (map union lst1 lst2) '()) ) Here's reduce from my lecture notes: (define (reduce op l id) (if (null? l) id (op (car l) (reduce op (cdr l) id)) )) ----------------------------------------------------------------------- 3.3 PROBLEM: (in-all-lists e lst) => returns #t if e is in every sublist of lst, #f/() otherwise. (lst is a list of lists.) Note: If lst is empty, then in-all-lists should return #f. Example: (in-all-lists 5 '((1 3 5) (2 5) (1 5 8))) => #t (in-all-lists 1 '((1 3 5) (2 5) (1 5 8))) => #f (in-all-lists 1 '()) => #f SOLUTION: (define (in-all-lists e lst) (cond ((null? lst) #f) (else (in-all-lists-helper e lst)) )) (define (in-all-lists-helper e lst) (or (null? lst) (and (member e (car lst)) (in-all-lists-helper e (cdr lst)))) ) * NOTE: - You can't use map on member here, because you have one element and a list of lists, not two lists of arguments that map could apply member to. - You need to use the helper procedure to get the base cases to work out right -- ie, if the list of lists is initially null, you must return false, but the recursive step on null list needs to return true. - You may feel more comfortable using cond in the helper procedure, but this is not as nice code. I prefer using cond (or if) in the main procedure, as it emphasize the special case of the initial null list. Another option that is fine is a combination of cond and 'and' in the helper procedure. Using cond and 'and' (good): (define (in-all-lists-helper e lst) (cond ((null? lst) #t) (else (and (member e (car lst)) (in-all-lists-helper e (cdr lst)))) )) Using cond only (not so good): (define (in-all-lists-helper e lst) (cond ((null? lst) #t) ((member e (car lst)) (in-all-lists-helper e (cdr lst)))) (else #f) )) =========================================================================== 4. Recall, there are 3 ways to improve efficiency as discussed in class: - let for local variable bindings to avoid extraneous recomputation and to make code cleaner - helper procedures to avoid extraneous recomputation and to make code cleaner - the use of accumulators, as exemplified in class