Homework 8

Due Date: Friday March 19, 9pm

Purpose To practice using list abstractions and local scopes

Expectations

This is a pair assignment. Remember that working in pairs means that you both work on the problems together, ideally by one person developing the solution, while the other person observes and comments. After a while, you switch roles. Working in pairs does not mean to divvy up the work between the two of you.

As with all assignments, you must upload one .rkt file (for the entire pair/team), in the language specified at the top of the assignment to the Handin Server. For this assignment, you must use ISL. Using the wrong language will invalidate your submission and result in a score of 0, so please be careful.

Unless otherwise stated, all data and functions you design must be designed according to the data and function design recipes, resp., following all four steps in each case.

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 please remember to read it before submitting each assignment.

-----------------------------------------------------------------------------

This assignment focuses on more applications of list abstractions, and specifically, those that benefit from use of local. Unless stated otherwise, each execise will involve using one or more list abstractions in some combination. Now that you know how to use local, you are even more strictly required to use abstractions in such cases. They might require writing additional helper functions: you should apply the usual design recipe for each of those. Points will be deducted if you did not use list abstractions where it would have clearly helped.

You must also practice good design principles now that you know about local: if helper functions are not of general use, define them inside a local.

Also, read Piazza post 381 about the kinds of functions of ISL you are not allowed to use. You are allowed to use length, though you should be aware that length traverses the entire list (some of the exercises concern avoiding the cost of a list traversal).

Exercise 1 Design the function all-in-range that takes four arguments:

• a predicate function that takes two arguments of type X and returns #t if its first argument is less than its second argument

• a lower-limit value from X

• an upper-limit value from X

• a list of values from X

Function all-in-range returns #t if all of the items in the list are between the lower and upper limits; otherwise #f. Make your function parametric in X.

Exercise 2 Design the function first-n-evens that uses the list abstraction build-list to create a list of the first n positive even numbers (so, starting with 2, not 0).

Exercise 3 You are trying to write a function generate-n-randoms that generates a list of n random numbers, all in the range 0 .. n-1, inclusive. You recall there being a function random (look it up in the textbook to refresh your memory), and use it in the following first attempt:

(define (generate-n-randoms n)

(local [(define (random-x x)

(random (+ x 1)))]

(build-list n random-x)))

At first glance, this seems to work, but then you notice the earlier numbers seem to consistently be on the smaller side, and larger numbers only appear later in the list, though there are also many small numbers later in the list, too. Your partner agrees with your suspicions. This is not the behavior you wanted: your goal was to generate a random mix of large and small numbers in the desired range evenly distributed throughout the list. Explain why you think this inbalance occurred? (Yes, we are looking for an explanation here, not code!)

Exercise 4 Redesign the code from the previous exercise so that it fixes the problem you spotted. While you’re at it, follow the complete design recipe (we were being lazy when we wrote up that exercise). Use check-random to test your function.

For the next three exercises, you are given the following data type definition:

(define-struct webpage [url links])

; A Webpage is a (make-webpage String [List-of String])

; Represents a webpage with a URL and a list of outgoing links.

(define wp-1 (make-webpage "Page1" (list "Page2" "Page3")))

(define wp-2 (make-webpage "Page2" (list "Page1" "Page3")))

(define wp-2-bad (make-webpage "Page2" (list "Page1" "Page3" "Page4")))

(define wp-3 (make-webpage "Page3" (list "Page1")))

(define wp-3-bad (make-webpage "Page3" (list "Page1" "Page5")))

(define (wp-temp wp)

(... (wp-url) ... (list-temp (wp-links))))

URLs are typically fancy, specially-formatted strings, but for our examples, we just plugged in simple strings (i.e., they don’t look like "http::/foo/fee"). That shouldn’t affect any of the functions we will write.

Exercise 5 Design the function busy-pages that takes a [List-of Webpage] and a page count limit, and returns a list of those pages that have more than that number of outgoing links. You must use the filter list abstraction for this exercise.

Exercise 6 Design the function busy-page/v2 that performs the same task as the preceding exercise, but uses the foldr list abstraction. You can copy and adapt the parts of the design recipe from your previous solution that are similar or identical.

Notice that this exercise asks you to use foldr and return a list.

Exercise 7 Design the function bad-links that scans a list of Webpages, and returns a list of the outgoing links in the webpages that are to pages not in the list (self-links are allowed). You should return a flat list, not a list-of-lists. You must use list abstractions, and are not allowed to write any recursive list-processing functions. Duplicates are allowed in the result.

Exercise 8 Design a function even-product that takes a non-empty list of positive integers, and returns their product if and only if all of the numbers in the list are even. If any number in the list is odd, return 1. For efficiency reasons, we impose the following restrictions on your implementation:

First, you can only traverse the list once. That implies you are not allowed to first pre-scan the list to check that every number is even–that would be too inefficient (recall we made that kind of optimization to avoid a call to filter followed by length–the case here would be even worse.)

Second, you must make judicious use of local to make your implementation efficient. Recall the problem with our initial recursive implementation of maxnum–you will likely face the same problem here. Your implementation must be able to process a list of at least 30 numbers. Also, try a mix of different cases: recall that our maxnum performance varied dramatically not just with the list length, but with the order of the input values.

Finally, for this exercise only, your solution should be function(s) based on the standard list template. In fact, little credit will be given if you use any of the list abstractions outlined in Fig. 95 and 96 in the textbook in your code. (Those include filter, map, foldr/l, andmap, ormap, and build-list. You are allowed to use build-list to create your test cases, though.) Also, a reminder that you are not allowed to use the remove function, as per the Piazza POST.