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?
Vectors.
Probably more with pairs and pair structures (although, since I didn't return the last quiz, that's probably not fair).
Maybe something about color and design or the sample projects.
What kinds of questions might you ask?
What design elements do you see in this image?
What approach do you think the authors used in this image? Did they use image-compute or gimp tools or drawings-as-values or ....?
"Given this partially completed vector procedure, fill in the blanks."
"Show the steps when I apply this procedure to *this input."
"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.)
Contrast different kinds of vectors, and contrast vectors and lists.
Can you go over the recursive sum procedure for vectors?
Start with patterns
(define PROC
(lambda (vec)
(let kernel ([pos 0])
(if (= pos (vector-length vec))
BASE-CASE
(COMBINE (vector-ref vec pos) (kernel (+ pos 1)))))))
(define PROC
(lambda (vec)
(let kernel ([pos 0]
[so-far START])
(if (= pos (vector-length vec))
(FINAL-MODIFICATION so-far)
(kernel (+ 1 pos)
(COMBINE (vector-ref vec pos) so-far))))))
Convert them as appropriate
(define vector-sum-1
(lambda (vec)
(let kernel ([pos 0])
(if (= pos (vector-length vec))
0
(+ (vector-ref vec pos) (kernel (+ pos 1)))))))
(define vector-sum-2
(lambda (vec)
(let kernel ([pos 0]
[so-far 0])
(if (= pos (vector-length vec))
so-far
(kernel (+ 1 pos)
(+ (vector-ref vec pos) so-far))))))
How does this work?
(vector-sum-1 #(3 4 5))
(kernel 0)
(+ 3 (kernel 1))
(+ 3 (+ 4 (kernel 2)))
(+ 3 (+ 4 (+ 5 (kernel 3))))
(+ 3 (+ 4 (+ 5 0)))
(+ 3 (+ 4 5))
(+ 3 9)
12
Why don't we just use something like (sum (vector->list vec))
?
That's much easier for the programmer, so it's good.
However, it means that we have to build a list, which requires time and space.
For the lab, you learn more by writing the procedure recursively.
And that approach fails you for some things
(define vector-double-bad!
(lambda (vec)
(list->vector (map (l-s * 2) (vector->list vec)))))
Predicted output
> (define vec1 (vector 3 4 5))
> (vector-double-bad! vec1)
NO OUTPUT
> vec1
'#(6 8 10)
Whoops! Doesn't mutate the vector like it's supposed to.
Why do we say "mutate" rather than "change" or "modify"?
Tradition. But I'll ask around.
Consider the following definitions
(define vec1 (vector 3 4 5))
(define vec2 #(4 5 6))
(define vec3 (make-vector 4 3))
(define vector-double!
(lambda (vec)
(let kernel! ([pos 0])
(when (< pos (vector-length vec))
(vector-set! vec pos (* 2 (vector-ref vec pos)))
(kernel! (+ pos 1))))))
What output would you expect from the following?
> vec1
'#(3 4 5)
> vec2
'#(4 5 6)
> vec3
'#(3 3 3 3)
> (vector-double! vec1)
NO OUTPUT
> (vector-double! vec2)
NO OUTPUT
> (vector-double! vec3)
NO OUTPUT
> vec1
'#(6 8 10)
> vec2
'#(8 10 12)
> vec3
'#(6 6 6 6)
Lesson: Vectors created by #(4 5 6)
are immutable: You can't use
vector-set!
with them.
Next question: Fill in the blank to achieve the vector-sum procedure
(define vector-sum
(lambda (vec)
(let kernel ([pos 0])
(if (= pos (vector-length vec))
_____
(_____ (vector-ref vec _____) (kernel _____))))))