Homework 9
Due Date: Thu April 30, 10pm
Purpose To practice using lists; explore abstractions
Expectations
This is another pair assignment; you will be working with your new partner.
As with all assignments, you must upload one .rkt file in the language specified at the top of the assignment to the Handin Server. For this assignment, you must use ISL (remember to correctly set the mode in DrRacket). 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 design recipe. However, you cannot always use a template to guide you in the design of a function that employs one of the functional abstractions, such as map, filter, etc. – you have to think at a higher level.
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.
Some functions may require helper functions, defined separately or defined internally with a local so that the internal function can reference the main function’s parameters. 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. If you prefer to use lambda expressions instead of defining named helper functions, you may also do that.
Points will be deducted if you did not use list abstractions where it would have clearly helped.
-----------------------------------------------------------------------------
This assignment covers two broad areas: more advanced processing of ISL lists, and using abstraction to factor out the common parts of functions by parameterizing the differences with values and functions as arguments.
In this and future homeworks, when using lists, you can just start using a data definition like [ListOf Foo] without having to define that list data definition first (but you will need to have defined the data definition Foo, unless it is built-in).
We will first start with some more interesting list-processing tasks:
Exercise 1 Design the function str-in-list-even?/v1, which determines if a given string occurs in a list of strings an even amount of times. Your implementation should count up the number of instances and then determine if this count is even. (As stated in the intro to this homework, you no longer have to separately define [ListOf String] to use it.) ISL has a built-in function even?.
Exercise 2 Now, design the function str-in-list-even?/v2, which utilizes the following observation: notice that each time the supplied string occurs in the list, if the previous result was #t, the new result is #f, and vice versa. You do not need to re-design your data and are welcome to re-use the tests from the previous problem.
Exercise 3 Here is the code we developed in class for do-to-all:
; do-to-all : (X Y) [X -> Y] [ListOf X] -> [ListOf Y] ; Applies the first argument function to each number (check-expect (do-to-all add1 '()) '()) (check-expect (do-to-all add1 (list -4 100)) (list -3 101)) (check-expect (do-to-all sqr (list -4 100)) (list 16 10000)) (define (do-to-all f lon) (cond [(empty? lon) '()] [else (cons (f (first lon)) (do-to-all f (rest lon)))])) Adapt it into a design for the function do-to-all-if, which takes as an additional parameter a predicate test. Each item in the list should first be tested with test, and if it returns true, that item should be processed through the mapping function. If the predicate returns false, the original item should be added to the result unprocessed (not dropped!). For example:
(check-expect (do-to-all-if negative? sub1 (list 10 -10 -20 20)) (list 10 -11 -21 20)) Here, negative? is a built-in function that returns true if the argument is less than 0.
Exercise 4 Design the function concat-all-strs, which concatenates (joins together) all of the strings in a list.
Exercise 5 Design the function biggest-number, which returns the largest number in a list of non-negative numbers, or 0 if the list is empty.
Exercise 6 In some academic journals, which come out monthly or even weekly, page numbering is reset only at the first volume of the year. So, the January volume might contain pages 1-120, the second volume might have pages numbered 121-255, the third volume pages 256-257 (not much happened that month), etc. Assume you started your subscription part-way through the year, so the earliest volume you have might start at some page higher than 1, but you do have all the volumes for the remainder of the year. You are given the starting page numbers of the volumes you own, in chronological order, as a list of numbers. (So, the numbers in the list would occur in increasing order.)
Design the function page->volume, which takes a page number, and returns the volume number in your collection, starting from 1, that contains that page, or 0 if the requested page is before the first volume in your collection. For example:
(check-expect (find-volume 150 (list 101 201 301)) 1) (check-expect (find-volume 300 (list 101 201 301)) 2) (check-expect (find-volume 301 (list 101 201 301)) 3) (check-expect (find-volume 999 (list 101 201 301)) 3) (check-expect (find-volume 1 (list 101 201 301)) 0) ; volume not found
Exercise 7 Design the function all-in-range that takes four arguments:
a predicate function that takes two arguments with data definition 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.
Show how you could use your function to tell if a list of strings contained only strings in the range "aardvark" to "banana". (So the string "cat" or "zebra" would disqualify any list in which it appeared, for example.)
Exercise 8 Design the function union that takes two sets of numbers, and produces the union of the two sets: the set containing every number that occurs in either set.
For our purposes, we will represent a set of numbers as a list of numbers, where repetitions are not allowed.
Recall the functions we defined in class for operating on numeric sets, for example:
; NumSet = [ListOf Number] ; Order of items in the list irrelevant; repetitions not allowed. ; NumSet Number -> Boolean ; Is the number a member of the set? (define (contains? s n) (ormap (lambda (elt) (= elt n)) s)) ; Add the element e to set s. ; Number NumSet -> NumSet (define (elt+set e s) (if (contains? s e) s (cons e s)))