CSC151.02 2003F, Class 39: Discussion of Exam 2 Admin: * Preregister for CSC152! Overview: * Problem 1 * Problem 2 * Problem 3 * Problem 5 * Problem 4 Problem 1: eqv? vs. equal? * Key difference: * eqv? uses "memory locations" * equal? looks at the contents and compares them * Why not use equal? * Because it takes a long time to look at two structures * Because you expect that when you change one thing that's equal to another, both will change Problem 2: in-tree? * Goal: Test your knowledge of deep recursion * What's the key feature of deep recursion? * Need a base case * Recurse on both the car and cdr of a pair * Observation: You need deep recursion for tree structures * Questions? Problem 3: list-of-symbols->string * Goals: List recursion, Special cases, Use of strings * Key issues: * Dealing with empty list * Putting parentheses around the whole thing * Not putting an extra space in at the end * Dealing with empty list (if (null? list-of-symbols) "()" (kernel list-of-symbols)) ; Kernel gets to deal with non-empty list * Putting parentheses around the whole thing (string-append "(" "a b c" ")") (string-append "(" (kernel list-of-symbols) ")") ; Kernel gets to deal with non-empty list * Our kernel does not need to handle the parens or empty lists (define kernel (lambda (lst) ; Base case: Singleton list (if (null? (cdr lst)) ; If the list has only one element, the string version (w/o parens) is .. (symbol->string (car lst)) ; Otherwise (string-append (symbol->string (car lst)) " " (kernel (cdr lst)))))) Problem 5: number->digits * Key idea: Numeric recursion * Problem: Special case of 0 * What are the typical patterns of numeric recursion? * The one from factorial (define PROC (lambda (val) (if (zero? val) BASE (COMBINE val (PROC (- val 1)))))) * The one from "digit-of?", "num-digits", etc. (define PROC (lambda (val) (if (zero? val) BASE (COMBINE (remainder val 10) (PROC (quotient val 10)))))) * Let's try the latter (define kernel (lambda (val) (if (zero? val) null (cons (remainder val 10) (kernel (quotient val 10)))))) (define number->digits (lambda (val) (reverse (kernel val)))) Problem 4: Checking preconditions * Strategy 1: Husk and Kernel * Strategy 2: Step-at-a-time (define in-tree? (lambda (symbol tree) (letrec ((in-tree-kernel? (lambda (tree) INSERT_OLD_CODE_HERE)) (symbol-tree? (lambda (tree) (or (null? tree) (symbol? tree) (and (pair? tree) (symbol-tree? (car tree)) (symbol-tree? (cdr tree)))))) (cond ((not (symbol? symbol)) (error 'in-tree? "first arg not a symbol")) ((not (symbol-tree? tree)) (error 'in-tree? "that's not a tree")) (else (in-tree-kernel? symbol tree)))))) (define in-tree? (lambda (symbol tree) (cond ((symbol? tree) (eqv? symbol tree)) ((pair? tree) (or (in-tree? (symbol (car tree))) (in-tree? (symbol (cdr tree))))) ((null? tree) #f) (else (error 'in-tree? "that's not a tree"))))) Which is better? * The second is more "efficient" because it doesn't waste time looking at the whole tree when the kernel may find the correct value in the first step or so. * In the first, after you finish checking, you never have to think about it again. (It segments your work.) * First one is prettier/easier to read. How would you get started on solving these problems? * Some key strategies * Decompose the problems into simpler problems * E.g., ignore the parens, ignore the special cases * Find similar problems you've solved and reuse those ideas * E.g., number->digits is like digit-of or count-digits * Make a list of procedures that seem relevant * E.g., realize that string-append is likely to be useful * For tests: Figure out what key principles Sam is testing * Expect some fumbling around * When all of those fail ... * Limit the amount of time you "hit your head against the wall" * Come ask for help