Week 7 Set b

Due Date Wednesday 10/16 at 9:00pm (Week 7)

Purpose To design and use abstractions.

Watch Your Language

As stated above, this is to be submitted in ISL, not ISL with Lambda. We want to ensure you are fully comfortable with local before moving on to λ.

Finger Exercises

Exercise 1 From HTDP, 254 255 265 266

Graded Exercises

Exercise 2 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.

Note: For all of the following exercises, be sure to use the appropriate pre-defined abstraction.

Exercise 3 Design a function scalar-matrix which given a natural number n and a number k, outputs an nxn matrix (list of list of numbers) where the diagonal (first element of the first row, second element of the second row... nth element of the nth row) entries are k and the other elements are 0.

; A Network is a [List-of Person]

; A Person is a (make-person String Pet [List-of String])

(define-struct person [name pet friends])

; and represents their name, their type of pet, and the name of their friends

; assume all of the names in the network are unique, and that the names of friends are unique

; and represent actual people in the network

; A Pet is one of:

; - "dog"

; - "cat"

(define NETWORK

(list

(make-person "Alice" "dog" (list "Carol" "Heidi"))

(make-person "Bob" "cat" (list "Carol" "Dan"))

(make-person "Carol" "dog" (list "Alice"))

(make-person "Dan" "cat" (list "Carol" "Eric" "Frank" "Grace"))

(make-person "Eric" "dog" (list "Alice" "Bob" "Carol" "Dan" "Frank" "Grace"))

(make-person "Frank" "cat" (list "Alice" "Bob" "Carol" "Dan" "Grace"))

(make-person "Grace" "dog" (list "Bob" "Frank"))

(make-person "Heidi" "cat" (list "Alice" "Bob" "Carol" "Dan" "Eric" "Grace"))))

; get-person : Network String -> Person

; Get the person in the network (assume they are there)

(define (get-person n s)

(cond [(string=? s (person-name (first n))) (first n)]

[else (get-person (rest n) s)]))

(check-expect (get-person NETWORK "Bob") (make-person "Bob" "cat" (list "Carol" "Dan")))

Exercise 4 Design the function update-network which takes a Network and updates every individual’s pet to become the pet the majority of their friends have. If there is no majority amongst their friends (a tie), then their pet is unchanged. Note that this update is atomic which means everyone’s pet updates at once based only on the previous network’s state. In other words, where someone appears in the network should have no effect on the update process.

Exercise 5 Design the function bubbled? which determines if a person (given to the function as just their name) is only friends with people who have their same pet.

Exercise 6 Design the function bubble which removes everyone from a given Network who does not have a given Pet. Be sure to update people’s friends as needed. To recieve full credit for this problem, all Networks returned by a loop (i.e. when foldr finishes evaluating) must uphold the invariants on a Network, especially in regards to the names of friends being in the Network.