Homework 7
Due Date: Thursday February 27, 9pm
Purpose: To practice the use of pre-defined list abstractions.
This is again a pair assignment. It suffices for one member per pair to submit the homework via the handin server (whatever is submitted last counts for the whole pair).
You must submit a single .rkt file containing your responses to all exercises via the Handin Server. We accept no email submissions.
You must use the programming language specified at the top of this page.
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 revisit it before submitting each assignment.
Unless otherwise stated, for all programming problems you must provide (i) a signature, (ii) a purpose statement, (iii) sufficiently many check-expects (not for big-bang programs), and (iv) the actual code, in the language specified at the top of this page.
Be sure to look at the feedback for previous assignments before submitting, as we will be grading you more strictly on things we have pointed out before.
Failure to comply with these expectations will result in deductions and possibly a 0 score.
(define-struct country [name capital population landlocked neighbors]) ; A Country is a (make-country String String Nat Boolean [List-of String]) ; repr. data on a country, where ; - name is the country's name ; - capital is the name of the country's capital ; - population is the (approx.) population of the country IN MILLIONS ; - landlocked is true iff the country does not have a coastline ; - neighbors is a list of names of all countries with which the country has a common border (define CO-0 (make-country "United States" "Washington" 330 #f (list "Canada" "Mexico"))) (define CO-1 (make-country "Japan" "Tokyo" 130 #f '())) (define CO-2 (make-country "Switzerland" "Bern" 9 #t (list "Germany" "Austria" "Lichtenstein" "Italy" "France"))) (define CO-3 (make-country "France" "Paris" 70 #f (list "Belgium" "Germany" "Switzerland" "Italy" "Spain"))) (define CO-4 (make-country "Argentina" "Buenos Aires" 50 #f (list "Paraguay" "Brazil" "Uruguay" "Chile" "Bolivia"))) (define (country-templ c) (... (country-name c) ... (country-capital c) ... (country-population c) ... (country-landlocked c) ... (country-neighbors c) ...)) (define-struct city [name country population megacity languages]) ; A City is a (make-city String String Nat Boolean [List-of String]) ; repr. data on a city, where ; - name is the name of the city ; - country is the name of the country to which the city belongs ; - population is the (approx.) population of the city IN THOUSANDS ; - megacity is true iff the city has a population of 1 million people or more ; - languages is a list of names of /natural/ languages (not ISL) officially spoken in that city. (define CI-0 (make-city "Washington" "United States" 5000 #t (list "English" "Spanish"))) (define CI-1 (make-city "Bern" "Switzerland" 500 #f (list "German" "French" "Rhaetian"))) (define CI-2 (make-city "Boston" "United States" 700 #f (list "English" "Spanish" "Chinese"))) (define CI-3 (make-city "Nairobi" "Kenya" 5000 #t (list "Swahili" "English"))) (define (city-templ c) (... (city-name c) ... (city-country c) ... (city-population c) ... (city-megacity c) ... (city-languages c) ...)) ; A Location is one of ; - Country ; - City ; repr. a geographic location. (define LOC-0 CO-0) (define LOC-1 CI-0) (define (location-templ l) (cond [(country? l) (... (country-templ l) ...)] [(city? l) (... (city-templ l) ...)])) ; An Atlas is a [List-of Location] ; A list of Country-ies and City-ies. ; (We are not providing a template, since this data is of the form, [List-of ...].) (define A-0 (list CO-0 CO-1 CO-2 CO-3 CO-4 CI-0 CI-1 CI-2 CI-3))
Disclaimer: while some moderate effort has been made for the above data on countries and cities to be "close to the truth", we do not claim 100% accuracy, and we certainly do not claim universal representation. All omissions (and all mistakes, if any) are unintentional. Please do not modify the above data examples – even if wrong – since this may affect the behavior of your code in some tests. Feel free to post comments to the instructors if you believe something is geographically outrageously incorrect.
Note that both structs country and city have a field name and a field population, and that the second field in struct city is a String representing the name of the Country to which the City belongs; do not conflate this field with the struct country of the same name. Our design is hierarchical; there is no ambiguity.
In the following exercises, you are expected to use list abstractions whenever possible. If you and your partner find it difficult to see what abstractions might apply, write your code without them, i.e. based on the templates of the data involved (which likely requires recursion), and then see which of the list abstraction functions we have studied the resulting code seems closest to. Chances are that, as you are writing your code, you will realize that this is something you have done many times before. Now rewrite your code using list abstractions. Do not turn in your code using recursion (unless this is the only version you have).
Exercise 1 Copy the above definitions into your homework file. Then create two more (reasonably diverse) examples of data of type Atlas. You do not have to create more Country-ies or City-ies, but you are free to do so. Use the two new Atlas examples, as well as A-0, in all of the following function design exercises.
Exercise 2 Design two functions countries and cities that each take an Atlas as input and return the list of Country-ies and City-ies, respectively.
Exercise 3 Design a function cities-us that takes an Atlas and returns the list of City-ies in the US contained in that Atlas.
Exercise 4 Design a function neighbors-germany that takes an Atlas and returns the list of Country-ies neighboring Germany contained in that Atlas.
Exercise 5 A recent census revealed that the information on languages spoken in any given City was hopelessly outdated and in fact changes rapidly. The Atlas publisher decided that it is no longer reliable to include such information in (the printed version of) their Atlas.
Design a function atlas-w/o-lang-data that takes an Atlas and returns the same, except that the language data on each City in the Atlas is replaced by the empty list. This is interpreted to mean that language data is not available, or is unreliable.
For your check-expects, define new "versions" of all City-ies that have an empty languages entry.
Exercise 6 Design a function countries-population that takes an Atlas and returns the total number of people "represented" in that Atlas, i.e. the combined population of all Country-ies in it, in millions.
Hint: This function can be written using only the three list abstractions we have studied, and in fact all of them together!
Exercise 7 One of the Atlas’ publisher’s employees found out that, in some version of an Atlas, there was a typo that resulted in the combined City population to exceed the combined Country population. The publisher decided: "That makes no sense!" Build a verifier function check-population: a tool that takes an Atlas and returns true if the total number of City people is at most the total number of Country people in the Atlas. Otherwise, i.e. if there is a violation of the above specification, your function should report an error using a formatted message of the form:
"check-population: error: atlas has 2000 thousand people in all cities but only 1 million people in all countries"
Exercise 8 This is not an exercise, but a request from us – and an opportunity for you: let us know how this class is working out for you so far. We will post a link to a short survey in the next few days on Piazza. Follow that link and take the survey. Then, in your homework submission, under Exercise 8, state, in comments:
; I filled out the halftime class survey.
A small amount of credit will be reserved for this activity. If you don’t state that you filled out the survey, you won’t get that credit. We apply the standard honor code here and trust your honesty.