Homework 4
Due Date Tuesday 10/5 at 9:00pm (Week 4)
Purpose To design functions with lists, maps, and errors.
Finger Exercises
You should submit a single .rkt file containing your responses to all graded exercises via the Handin Server. We accept NO email submissions.
You are only allowed to use the language specified at the top of this page: failure to do so will result in a 0.
All elements of the design recipe are expected. Data definitions should have associated interpretations, examples, and templates. Functions should have signatures, purpose statements, tests, and code.
Note that there are few exceptions to these rules, such as main functions not being able to be tested.
Be sure to use helper functions when appropriate to keep code clear.
Graded Exercises
Exercise 2 Design a function not-present? which, given a list of integers and an integer i, checks if i does not occur in the given list.
Exercise 3 Using not-present?, design a function all-unique? which checks if every number in a list of integers is unique and appears in the list exactly once.
Exercise 4 Design a function has-even-count? which, given a list of integers and an integer i, checks if i occurs in the list an even number of times.
Exercise 5 Consider how you might “do the same thing” and use has-even-count? to design a function all-even-count?. In a comment, explain why the approach you used for designing all-unique? cannot work, and speculate what you think might be needed to design this function.
Love Thy Neighbor
Exercise 6 Consider the streets of a gridded city like Manhattan, with roads running east/west and north/south. For simplicity, we’ll assume all the streets have numbers instead of names. We want to work with the intersections of roads, which we’ll represent with a (make-posn Integer Integer). Design a function which given one of these intersections outputs its four neighbors, directly to the east, west, north, and south. You may assume the given coordinates are always between 0 and 99 (inclusive), but you must make sure to return only the neighbors where both coordinates lie above -1 and below 100.
Be sure to define any data definitions you might need for this problem and to follow the design recipe the entire way through.
Double Or Single Bag?
; A GC (GroceryCatalogue) is one of: ; - '() ; - (cons CE GC) ; where each catalogue entry has a unique name ; A CE (CatalogueEntry) is a ; (make-ce String Cost) (define-struct ce [name cost]) ; and represents the name of a food and how much it costs ; A Cost is one of: ; - (make-unit Number) ; - (make-lb Number) (define-struct unit [cost]) (define-struct lb [cost]) ; and represents either the cost per unit or per lb of an item ; A Checkout is one of: ; - '() ; - (cons Order Checkout) ; A Order is one of: ; - String ; - (make-weight String Number) (define-struct weight [name lb]) ; and represents either one unit of food or its name and weight in lbs
While a GC is certainly a list, this kind of data is often referred to as a map (for which mapping, hash, and dictionary are all synonyms depending on the language you are in). A map is a type of data that associates pieces of one type of data with another; in this case, foods with their costs. Maps are ubiquitous throughout computer science, and you may even find them come up again in this course!
Exercise 7 Define examples for and the template of each of the above data definitions.
Exercise 8 Design a function get-cost, which given the name of a food and a GC gets its associated Cost. If no Cost is found, return an informative error.
Exercise 9 Design a function set-cost, which given the name of a food, a Cost, and a GC returns the catalogue with that food’s Cost now set to the given one.
Exercise 10 Design the function average-unit-cost, which given a GC, produces the average cost of items that are priced per unit. If there are none, return an informative error. The number of items that are priced per unit should only be computed once!
Exercise 11 Design the function express-lane?, which determines if a Checkout has 10 items or fewer.
Hint: for testing purposes, one can use make-list to make large lists quickly.
Exercise 12 Design the function total-cost, which given a Checkout and a GC produces the total cost. If a food has been weighed that is priced by unit or if a food that is priced by pound has not been weighed, return an informative error.