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