Homework 6

Due Date Tuesday 10/19 at 9:00pm (Week 6)

Purpose To practice abstracting different versions of functions and using abstractions, and to begin using higher-order operations.

Language change!

As noted above, please submit this assignment in Intermediate Student Language as opposed to BSL+.

Finger Exercises

Exercise 1 From HTDP, 250 252 254 255 265 266

We strongly recommend completing the following finger exercises.

Exercise 2 Revisit the GC data definition from two weeks ago. Design the function update-gc, which given a GC, the name of a food, and a [Cost -> Cost] function, applies that function to the previously associated cost of that food and leaves the rest of the catalogue untouched. If no such food was present, make a reasonable decision about what to do (there are at least two).

Exercise 3 Imagine, for a moment, you are a real-estate website programmer. One crucial data definition would be that of a House:

; A House is a (make-house String Number Number String Number)

(define-struct house [address bedrooms bathrooms style value])

Actual real estate data dealing with houses have much larger (and usually poorly designed) data definitions, but that’s not our problem. Now, which of these values is likely to change over time? Only the house’s cost.

Let’s imagine a scenario in which the market dictates all houses with 2.5 or more baths become worth 1.1 times their current value, those with 2 or fewer bedrooms become worth 0.9 times their current value, and those with a "Colonial" style are all increased by 500 dollars. If more than one of these scenarios apply, then only the first one (as listed here) takes effect; if none do, nothing changes.

To implement this,

1. design a function that given a house and a [Number -> Number] function applies it to the house’s cost (and leaves the rest of the house as it is). Then,

2. demonstrate the usefulness of the function you just defined by using it in a function which applies the above scenario to a single house. Then,

3. demonstrate the usefulness of pre-defined list abstractions (listed below) by using one of them and the function you just defined to apply the above scenario to a list of homes.

Graded Exercises

Exercise 4 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

(define (sum-x-coords lop)

(cond

[(empty? lop) 0]

[(cons? lop)

(+ (posn-x (first lop))

(sum-x-coords (rest lop)))]))

(check-expect (sum-x-coords empty) 0)

(check-expect (sum-x-coords

(cons (make-posn 3 4)

(cons (make-posn 5 12)

empty))) 8)

; mult-distances : [List-of Posn] -> Number

; Multiply all the distances from each position to the origin

(define (mult-distances lop)

(cond

[(empty? lop) 1]

[(cons? lop)

(* (distance-to-origin (first lop))

(mult-distances (rest lop)))]))

(check-expect (mult-distances empty) 1)

(check-expect (mult-distances

(cons (make-posn 3 4)

(cons (make-posn 5 12)

empty))) 65)

; distance-to-origin : Posn -> Number

; Produces the distance from this position to the origin

(define (distance-to-origin p)

(sqrt (+ (sqr (posn-x p)) (sqr (posn-y p)))))

(check-within (distance-to-origin (make-posn 2 2)) (sqrt 8) 1e-6)

(check-expect (distance-to-origin (make-posn 3 4)) 5)

1. Abstract sum-x-coords and mult-distances. Be sure to re-define the functions using your new abstraction.

2. Use your new function to design the function strings-length, which sums the length of all of the strings in a list of strings.

3. Next, use the same 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 5 Design the function earliest, which takes a non-empty list of strings and a function (that takes two strings and outputs a Boolean, and 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. You must define and use a parameterized data definition [NEL-of X] (non-empty list of X).

Then, use earliest to define three other functions:

1. One that produces the string that comes earliest lexicographically (i.e., which would come first in a dictionary). Hint: string<? is quite useful.

2. One that produces the string that comes last lexicographically.

3. One that produces the last string in the non empty list.

Exercise 7 Sometimes we want to group 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 group cups by their capacity in fluid ounces, in which case we’d have the following collection of groups:

• 10: CUP1 and CUP3

• 8: CUP2

• 6: CUP4

Alternatively, we could group 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 group - we’ll refer to the distinct values of this characteristic as the "keys" of the grouping (e.g., 10, 8, 6 in the first example). Each entry in the result, i.e. one group of the grouping, has a key as well as a list of the original items having that key (in the same order they appeared in the original list).

Design the function create-grouping that takes in 3 arguments - a list of elements, a key extractor, and a key equivalence relation - and produces a grouping.

A key extractor is a function that extracts information from an element to determine what group 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.

Exercise 8 Download this starter code (right click > Save As...). There, you will find a handful of data definitions and two functions. Above the two given functions (but below any data definitions needed), design a function which abstracts these two functions. Write at least one explicit test for it that operates over a different type of list than the two functions below. Then, rewrite the bodies of the two initial functions (deleting code as needed) and implement them in terms of your new function. The old tests should still pass.