Homework 6

Due Date: Friday March 5, 9pm

Purpose To practice using lists; explore abstractions

Expectations

This (and all future homeworks) will be pair assignments. 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. Working in pairs does not mean to split up the work between the two of you.

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 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 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 type like [List-of Foo] without having to define that list data type first (but you will need to have defined the data type Foo, unless it is built-in).

We will first start with some more interesting list processing tasks:

The first set of exercises involves processing hexadecimal number strings. Recall the hexadecimal number system from Homework 4: hex numbers consist of the digits 0 thru 9, as well as the letters A thru F, representing values 10 thru 15, respectively.

Exercise 1 Define a new data type HexChar, which will be single-character strings with the 16 possible hexadecimal symbols, e.g. "7" or "B". (We are only allowing capital A-F). Note this is different from the representation you used in HW4, where the values 0-9 were stored as numbers. So this would be a simple enumeration, albeit a slightly long one.

Exercise 3 Design the recognizer function hexchar? that accepts a 1String, and returns true if the input is a legal hexadecimal character.

Exercise 4 Design the function hexchar->num that accepts a HexChar, and returns its numerical value (so, an unsigned number in the range 0-15–you do not have to define a new data type for this range).

Exercise 5 Design the function hexstr->num that converts a string of hexadecimal characters to its numerical equivalent. For example, if the input is "1F2", you would return 498 (1 * 162 + 15 * 16 + 2). If the input string has any characters other than the 16 legal hexadecimal values, you should return -1. (This is a good error value to return because our hexadecimal numbers are unsigned, so -1 will never occur as a "regular" outout. However, you need to take this into account in your signature.)

The function should work by first turning the input string into a list of individual characters by using the function split-str you wrote for the previous exercise. (If you could not get that working, you can use the built-in ISL function explode, but it would be much more rewarding to use your own!)

Then process the list of 1Strings into a composite cumulative numerical value. Use the functions hexchar? and hexchar->num you wrote earlier to help do this.

HINT: Your job will be much easier if you reverse the order of the list before processing it! ISL provides a built-in function reverse that does exactly that. Think about the fact than when you recursively process a list, you are actually processing the list from the end first, since that last recursive call is the first that returns. Then think about the relationship between the value represented by "123" and the value represented by "1234": 1234 = 123 * 10 + 4 (this is base 10, but the principle applies to any base).

Later, we will learn a better way to do tasks like this, where we don’t have to pre-reverse the list first... but you haven’t learned that yet, and you’re not allowed to use that technique here... but, soon!

Be careful and precise about types and signatures: hexstr->num must be able to deal with strings that have non-hex characters, so its input type is actually any String.

Don’t worry about efficiency: specifically, redundant calls to functions; we’ll address that problem in class soon!

Okay, moving on from hexadecimal number: more fun with lists!

Exercise 6 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 List-of String to use it.) ISL has a built-in function even?.

Exercise 7 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 true, the new result is false, 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 8 Here is the code we developed in class for do-to-all:

; do-to-all : (X Y) [X -> Y] [List-of X] -> [List-of 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) '()]

[(cons?  lon) (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 p?. Each item in the list should first be tested with p?, 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 9 Design the function concat-all-strs, which concatenates (joins together) all of the strings in a list.

Exercise 10 Design the function find-biggest-number, which returns the largest number in a list of non-negative numbers, or 0 if the list is empty.

Exercise 11 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 be sorted.)

Design the function find-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