Functional Problem Solving (CSC 151 2014F) : EBoards
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Setup] [VM] [Errors] - [Functions A-Z] [Functions By Topic] - [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2014S)] [Weinman (2014F)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)]
What's on the quiz?
Recursion (over lists)
More Recursion (using helpers)
And More Recursion (over numbers)
Husk/Kernel
Named Let and Letrec
Characters and strings
What kinds of questions might you ask?
"Read this recursive procedure and tell me what's wrong with it."
"Given this partially completed procedure, fill in the blanks."
"Show the steps when I apply this procedure to *this input."
"Here's documentation for this procedure. We've written a partial test suite. Please add two more useful tests that stress the procedure in different ways."
"Read this procedure, tell me what it does, give me the preconditions, and rewrite it so that it's clearer. (Probably only two of the three.)
Can you talk to us about base cases? How do you decide what they are and when to have them?
Reminders: Really general forms for recursive procedures
(define PROC
(lambda (PARAMS)
(if (SIMPLE? PARAMS)
BASE-CASE
(COMBINE (PART-OF PARAMS) (PROC (SIMPLIFY PARAMS))))))
(define PROC
(lambda (PARAMS)
(HELPER (MOST-OF PARAMS) (PART-OF PARAMS))))
(define HELPER
(lambda (REMAINING SO-FAR)
(if (SIMPLE? REMAINING)
(SOMETHING SO-FAR)
(HELPER (SIMPLIFY REMAINING)
(COMBINE (PART-OF REMAINING) SO-FAR)))))
Issue one: When are things simple enough that we can stop? A few common cases:
Empty list
(null? PARAMS)
- is there a natural answer that you can give for the empty list.One-element list
(null? (cdr PARAMS))
- Do we need at least one value?0 or 1 (when doing numeric recursion)
Many more. If we're looking for a value in a list (e.g., an even number in a list of numbers), the base case can be "that value is the first number in the list". If we're counting from M to N, the base case is probably "our counter has reached N"
Once you've identified that you've reached the base case, how do you decide what to return? First question I ask myself: What type of value are we computing. If I'm trying to build a list, I need to return a list. If I'm trying to build a number, I need to return a number. If I'm trying to compute a color, I need to return that color.
If we're doing helper recursion, the base case almost always involves returning the
SO-FAR
value. One strategy: Just return that value and see what happens. If it looks good, you're done. If it doesn't look right, think about the relationship of what you get to what you want.
Can we do a long and complicated example?
Sure. Let's find the average of a list of irgb colors.
(define irgb-average
(lambda (colors)
Direct recursion vs. helper recursion vs. ???
Suppose I have the list
'((irgb 255 0 0) (irgb 100 100 100) (irgb 0 25 74))
Does computing the average of'((irgb 100 100 100) (irgb 0 25 74))
help me find the average of the whole list?Let's simplify the example. We just want to compute the average of a list of numbers. Suppose I have the list '(1 100 24 5). Does computing the average of
(100 24 5)
help me?The first average is
(/ (+ 1 100 24 5) 4)
. The second average is(/ (+ 100 24 5) 3)
. Dividing by three does not really help us compute something that requires dividing by four.So we either want to divide each by the length and then add them up, or add them up and divide by the length.
(define average
(lambda (nums)
(average-helper nums 0 0)))
(define average-helper
(lambda (remaining sum-so-far length-so-far)
(if (null? (cdr remaining))
(/ (+ (car remaining) sum-so-far) (+ 1 length-so-far))
(average-helper (cdr remaining)
(+ (car remaining) sum-so-far)
(+ 1 length-so-far)))))
Update one: Check for the empty list in advance
(define average
(lambda (nums)
(when (null? nums)
(error "average: requires a non-empty list of numbers"))
(average-helper nums 0 0)))
Update two: Make null the default case
(define average-helper
(lambda (remaining sum-so-far length-so-far)
(if (null? remaining)
(/ sum-so-far length-so-far)
(average-helper (cdr remaining)
(+ (car remaining) sum-so-far)
(+ 1 length-so-far)))))
Can you talk a bit more about husk and kernel?
Some procedures will fail miserably if you give them "bad" inputs. (Don't meet the preconditions). Instead of having weird errors appear, why not give a clear error message.
The husk does the error checking.
The kernel does the real work, assuming that the inputs are good.
Can you give a sample quiz question that involves strings?
Let's remove all of the vowels from a string. E.g., "Rebelsky" > "Rblsky"
Zeroeth step; Bring up the documentation on strings so that we can remember what procedures are available.
First step
(define remove-vowels
(lambda (str)
(if (null? str)
str ; or ""
(___ (?? str) (remove-vowels (??? str))))))
Recursion model: Suppose we successfully remove the vowels from "ebelsky", giving us "blsky". How do we get the "Rblsky".
(define remove-vowels
(lambda (str)
(if (null? str)
str ; or ""
(string-append (substring str 0 1)
(remove-vowels (substring str 1))))))
Whoops! Forgot to check if the first character is a vowel!
Whoops! Check for the empty string with
(equal? "" str)
, not with(null? str)
.
(define remove-vowels
(lambda (str)
(if (equal? "" str)
str ; or ""
(if (member (string-ref str 0) '(#\a #\e #\i #\o #\u))
(remove-vowels (substring str 1))
(string-append (substring str 0 1)
(remove-vowels (substring str 1)))))))