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?
Your classmates' pictures.
Maybe one or two extra-credit problems.
Why don't we get to take a quiz on recursion like the other section?
I always have to sneak in one "know your classmates" quiz. This seemed like a good time.
How do I write a local procedure so that I can apply the fold
pattern
for rgb-darkest
?
The fold pattern: Given an operation that combines two values into a single value, generalize it to work with a list of values. * sum: We know how to add two values; we can now add a list of values * list-join: We know how to append two lists; we can now append an arbitrary number of lists * Goal Given a list of colors, find the darkest
The pattern
(define FOLDED-OP
(lambda (lst)
; If the list has one value
(if (null? (cdr lst))
; Use that value
(car lst)
; Otherwise, recurse on the cdr and combine with the
; car using the operation
(OP (car lst) (FOLDED-OP (cdr lst))))))
Let's write
irgb-darkest
.
(define irgb-darkest
(lambda (lst)
; If the list has one value
(if (null? (cdr lst))
; Use that value
(car lst)
; Otherwise, recurse on the cdr and combine with the
; car using the operation
(OP (car lst) (irgb-darkest (cdr lst))))))
The OP should be "given two irgb colors, find the darker of the two".
(define irgb-darker
(lambda (color1 color2)
(if (< (irgb-brightness color1) (irgb-brightness color2))
color1
color2)))
We could also make it local
(define irgb-darkest
(let ([irgb-darker (lambda (color1 color2)
(if (< (irgb-brightness color1)
(irgb-brightness color2))
color1
color2))])
(lambda (lst)
; If the list has one value
(if (null? (cdr lst))
; Use that value
(car lst)
; Otherwise, recurse on the cdr and combine with the
; car using the operation
(irgb-darker (car lst) (irgb-darkest (cdr lst))))))
Here's a potential problem with the fold pattern. Can we use the
pattern to do difference
(generalize subtract?)
(define difference
(lambda (lst)
; If the list has one value
(if (null? (cdr lst))
; Use that value
(car lst)
; Otherwise, recurse on the cdr and combine with the
; car using the operation
(- (car lst) (difference (cdr lst))))))
> (difference (list 1 2 3 4 5 6))
-3
We expected -19 because 1 - 2 - 3 - 4 - 5 - 6 is -19. We got -3. Why? Because the way this is designed makes the operation right-associative.
We know how to make operations left-associative: Use a helper procedure. Should we write a left-associative difference and then find the pattern, or predict a pattern and the write the left-associative difference.
; Fold, but left
(define FOLDED-OP
(lambda (lst)
(FOLDED-OP-HELPER (car lst) (cdr lst))))
(define FOLDED-OP-HELPER
(lambda (so-far remaining)
(if (null? remaining)
so-far
(FOLDED-OP-HELPER (OP so-far (car remaining))
(cdr remaining)))))
; Fold, but left
(define difference
(lambda (lst)
(difference-HELPER (car lst) (cdr lst))))
(define difference-HELPER
(lambda (so-far remaining)
(if (null? remaining)
so-far
(difference-HELPER (- so-far (car remaining))
(cdr remaining)))))
Yay!