Homework 6
Due Date Friday, October 18 at 6pm
Purpose To practice abstracting similarities in functions.
You should submit a single .rkt file containing your responses to all exercises via the Handin Server. We accept NO email submissions. Failure to submit a .rkt file will result in a 0.
You are only allowed to use the language specified at the top of this page: failure to do so will result in a 0.
Your code MUST conform to the guidelines outlined in the style guide on the course website. The style guide will be updated as the semester progresses so please remember to read it before submitting each assignment.
You must follow all the steps of the design recipe when completing this assignment.
Please be sure to look at the feedback for assignment 4 before submitting, as we will be grading you more harshly on things we have warned you about before.
You must submit this assignment with your partner, assigned in lab on Tuesday, October 1st.
Graded Exercises
Exercise 1 For this exercise, you may assume the standard definition for Posn and [List-of Posn], and do not need to define them or their templates. You can if you want to, though.
Consider the following functions:
; sum-x-coords : [List-of Posn] -> Number ; Sum all the x-coordinates in the list of positions (check-expect (sum-x-coords empty) 0) (check-expect (sum-x-coords (cons (make-posn 3 4) (cons (make-posn 5 12) empty))) 8) (define (sum-x-coords lop) (cond [(empty? lop) 0] [(cons? lop) (+ (posn-x (first lop)) (sum-x-coords (rest lop)))])) ; mult-distances : [List-of Posn] -> Number ; Multiply all the distances from each position to the origin (check-expect (mult-distances empty) 1) (check-expect (mult-distances (cons (make-posn 3 4) (cons (make-posn 5 12) empty))) 65) (define (mult-distances lop) (cond [(empty? lop) 1] [(cons? lop) (* (distance-to-origin (first lop)) (mult-distances (rest lop)))])) ; distance-to-origin : Posn -> Number ; Produces the distance from this position to the origin (check-within (distance-to-origin (make-posn 2 2)) (sqrt 8) 1e-06) (check-expect (distance-to-origin (make-posn 3 4)) 5) (define (distance-to-origin p) (sqrt (+ (sqr (posn-x p)) (sqr (posn-y p)))))
Abstract sum-x-coords and mult-distances. Be sure to re-define the functions using your new abstraction.
Use your new function to design the function biggest-difference, which produces the largest difference between a posns’s x and y values in a list of posns. Note that the difference should always be taken as an absolute value, whether the x or y value is bigger.
Exercise 2 Design the function my-animate, a re-implementation of the animate function we used earlier in the class but this time using big-bang.
Exercise 3 Design the function earliest, which takes a non-empty list of strings and a function (that takes two strings and outputs a Boolean), which indicates whether or not the first string comes "before" the second one. The earliest function should output the string that comes earliest in the non-empty list according to the given function.
Then, use earliest to define three other functions:
One that produces the string that comes earliest lexographically (i.e., which would come first in a dictionary). Hint: string<? is quite useful.
One that produces the string that comes last lexographically.
One that produces the last string in the non empty list.
Exercise 4 Sometimes we want to bin items by a certain property. For example, let’s say we had the following definition for cups:
(define-struct cup [oz color material]) ; A Cup is a (make-cup NonNegNumber String String) ; and represents a cup's capacity in fluid ounces, color, and material (define CUP1 (make-cup 10 "brown" "wood")) (define CUP2 (make-cup 8 "brown" "ceramic")) (define CUP3 (make-cup 10 "red" "plastic")) (define CUP4 (make-cup 6 "clear" "plastic")) (define CUPS (cons CUP1 (cons CUP2 (cons CUP3 (cons CUP4 empty))))) We could bin cups by their capacity in fluid ounces, in which case we’d have:
10: CUP1 and CUP3
8: CUP2
6: CUP4
Alternatively, we could bin cups by their color, in which case we’d have:
"brown": CUP1 and CUP2
"red": CUP3
"clear": CUP4
Note that the only difference is what characteristic of the items we are using to bin - we’ll refer to the distinct values of this characteristic as the "keys" of the binning (e.g., 10, 8, 6 in the first example). Each entry in the result, a bin, has a key as well as a list of the original items having that key (in the order the were in the original list).
Design the function create-binning that takes in 3 arguments - a list of elements, a key extractor, and a key equivalence relation - and produces a binning.
A key extractor is a function that extracts information from an element to determine what bin it should belong to. In the first example given, it would be a function that takes a cup and produces its capacity.
An equivalence relation is a function that takes two elements and produces a Boolean indicating whether or not they are equal. In the second example, the key equivalence relation would be a function that tells us if two colors are equal.