Homework 9
Due Date: Thursday March 19, 9pm Monday, March 23, 9pm
Purpose To practice lambda and functions with multiple complex inputs.
This assignment is to be completed with your new homework partner. As before, it suffices for one partner 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.
Use list abstractions, as opposed to list recursion based on the template, unless the abstractions make the code complicated or inefficient (say they force you to pass over a list several times, while a single pass suffices).
Use lambda, as opposed to local, if the helper function you are designing is small and simple, so signature, purpose statement, and tests seem unnecessary. Use good judgment.
Note that lambda only allows you to define functions. If you want to define a local variable, for instance to avoid redundantly recomputing a value, you must use local.
Exercise 1 Revisit Exercise 2 from Homework 6 (function word-counts). This function counts words in a text, given as a list of words, and reports the counts in a list. For example, if the text is the list,(list "I" "really" "really" "don't" "know")
Copy the design of this function from Homework 6, or the list-abstraction version from Homework 8 (this is up to you), into your HW09 solution file. Make sure whatever design you use is correct.
The output of this function is rather inconvenient, for several reasons: first, if I want to know how often the word "don't" occurs in the given list (the fourth word in the sentence), I have to carefully count to the fourth element of the output list, to get to the right count (1, in this case). Second, words that appear several times in the sentence are counted several times. Imagine the extreme case that the sentence is(list "Hey" "Hey" "Hey" "Hey" "Hey" "Hey" "Hey")
(this is a good test case!).We will first approach these problems abstractly, by writing functions that can fix the respective problems in a much more general context than just for the word count task.
Design an abstract function zip that takes two arbitrary lists and "zips" them together. That is, it produces a list of TwoLists. A TwoList is a list of size 2. The first TwoList contains the respective first element of each list, the second TwoList contains the respective second element of each list, and so on. If one of the two lists runs out of elements, ignore the remaining elements of the other list. For instance, given (list 1 3 5 7) and (list 2 4 6), the output should be (list (list 1 2) (list 3 4) (list 5 6)); the 7 is ignored. According to this specification, what happens if one input lists is empty? Include an appropriate test case.
Begin with a proper data design for TwoList. Then design your zip function. "Abstract" means that your signature must be as general as possible.
Design an abstract function remove-dups that takes a [List-of X] and a comparison function (which returns true iff the two given X’s are considered equal) and returns the list without duplicates. Which one(s) of the duplicate elements, if any, you remove is up to you, but otherwise the order of the list elements should not be disturbed. (Think about what this means.)
Now apply these two abstract functions to the word-count problem: design a function word-counts-neat that returns the result of zipping the input list and the output list of word-counts, with duplicate entries removed, so we can easily determine how often a particular word occurs in the sentence.
Exercise 2 The ultimate goal of this exercise is to design a function that flips the order of neighboring elements in a list. This function fits into the topic of this past week, in the sense that the standard list template is not suitable to design this function. Why not? because the standard list template asks whether a list is empty or not. A non-empty list has at least one element, but to flip neighbors we need to have access to the first two elements, so "non-empty" is too little information to go by.
We solve this problem in two steps. Consider the following (peculiar!) data definition.
; A [ZOM-List-of X] is one of: ; - '() ; - (cons X '()) ; - (cons X (cons X [ZOM-List-of X])) ; repr. a list with zero, one, or more elements.
Complete the above partial data definition, by defining examples of a [ZOM-List-of X] and, in particular, by defining a template, called zomlox-templ. Also, give an example of an X and a list that is not a [ZOM-List-of X].
As a simple exercise, design the function len that takes in an arbitrary list and returns its length. Your design must be based on the template zomlox-templ. Give at least four check-expects. Then discuss whether the design can be simplified, and how (but be sure to include the unsimplified design in your submission).
Now that we know how this template works, use it to design the function flip-neighbors that takes in a [List-of Any] and flips the order of neighboring elements. If the list has odd length, perform the neighbor-flipping on all elements but the last, which is retained unchanged. For example, given (list 1 "a" 2 "b" 3), your function should return (list "a" 1 "b" 2 3).
Exercise 3 Consider the following data definition:
; A [Checklist Z] is a [List-of [Z -> Boolean]] ; repr. a list of tests (functions that test some property of a Z) (define CL-0 (list even? odd? zero?)) ; a [Checklist Nat] ; (we don't need to define a template since our DD ; is of the form [List-of ...]) Now design the function checklist->predicate that accepts a [Checklist Z] and returns a single predicate [Z -> Boolean] that returns true exactly if all predicates in the checklist return true.
Observe that your function returns a function! Keep this in mind also when you design your check-expects.