Homework 8
Due Date: Thursday March 12, 9pm
Purpose To practice the use of list abstractions with local.
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 do not accept 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 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.
In this homework you are expected to use list abstractions for all list manipulations that the exercises may ask you to do, whether it is mapping, filtering, folding, ormapping, or andmapping over a list. Now that we have local, this is possible.
Exercise 1 Design the function expand, which takes a natural number n and returns a list of length n. All elements of the return list are lists of natural numbers, as follows. The first list is (list 0). The second list is (list 0 1). The third list is (list 0 1 2), and so forth. For example:
(check-expect (expand 5) (list (list 0) (list 0 1) (list 0 1 2) (list 0 1 2 3) (list 0 1 2 3 4))) As always, write your code using list abstractions and local. Can this problem be solved with list abstractions but without local? Briefly explain.
Exercise 2 Repeat Exercise 2a. from Homework 6 (function word-counts), but this time using list abstractions, i.e. no recursion in your code. You can reuse the signature, purpose statement, and check-expects from Homework 6 (assuming you did them correctly).
Hint: this is only possible with local, and you need to be smart about it. Keep in mind that local expressions can be nested (in fact, sometimes they have to be).
Follow the Design Recipe for list abstractions using local (you do not need to show intermediate steps of this recipe) and the function design recipe for all functions you define locally. That is, give signature, purpose statement, and tests embedded in comments.
For the rest of this homework, we return to the Atlas example from Homework 7.
Exercise 3 Copy the data definitions from the top of that homework into your solution file for the present Homework, including the two examples of data of type Atlas that you defined in Exercise 1 of Homework 7. You can also define 2 new Atlases, but make sure you have at least three Atlases in total, including A-0 from Homework 7.
(There will be no points for this exercise, but we mark it as a separate Exercise so the graders can match actual exercises with your submitted solutions.)
Exercise 4 Remember the attentive employee from Homework 7, who found a typo causing confusion with the City and Country populations represented in an Atlas? That same employee found another problem (she was later awarded the employee-of-the-month medal): it is odd for an Atlas to contain a Country whose capital is not contained as a City in the same Atlas. Likewise, it is odd for an Atlas to contain a City whose Country is not contained in the same Atlas. In such cases, the Atlas must be expanded.
Do the first step, by designing a function missing-locations that takes an Atlas and returns, in any order, the list of all Country-ies and City-ies in it that suffer from the above problem. (You do not need to fix the problem. After all, we need to leave some work to the publisher.)
Hint: Since you need frequent access to the given Atlas, this exercise requires heavy use of local, possibly nested. Be systematic about it, and use the Design Recipe for list abstractions using local. (You do not need to show the steps.)
Also, make an effort to avoid repeated computation of the same expression – local gives you the power. For instance, if you need the Country-ies of the Atlas several times, don’t filter the Atlas repeatedly, which is wasteful.