Homework 6

Due Date: Thursday February 20, 9pm

Purpose To practice abstracting similarities in functions.

• 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 accept no 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 actual 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.

Failure to comply with these expectations will result in deductions and possibly a 0 score.

Exercise 1 For this exercise you are expected to use abstract functions (functions that take another function as one of their arguments, such as map and filter, but also abstract functions that you may define on your own) whenever possible.

Here are data designs for a Bit and a BitString.

; A Bit is one of

; - "0"

; - "1"

; repr. a bit.

(define B-0 "0")

(define B-1 "1")

"#;"

(define (bit-templ b)

(cond [(string=? b "0") ...]

[(string=? b "1") ...]))

; A BitString is a String over Bits

; repr. a bitvector (which is a technical term).

(define BS-0 "")

(define BS-1 "001")

(define BS-2 "101")

"#;"

(define (bitstring-templ bs)

(... bs ...))

BitStrings are used to represent bitvectors: sequences of bits, such as 1001.

• Design a function bl2bs, which takes a [List-of Boolean] and converts it into the corresponding BitString. "Corresponding" means that #t becomes "1" and #f becomes "0".

• Design a function bs2bl, which takes a BitString and converts it into the corresponding [List-of Boolean]. Make sure to apply Boolean simplification in this problem wherever applicable.

  Hint: consider the ISL function explode.

• In part d. below we need a function that compares two lists of Booleans for equality. Given what we have learned about abstract functions, we know that we can in fact solve a more general problem: namely, designing a function list=? that takes two [List-of X] as input, as well as a comparison function for type X, and returns whether the two [List-of X] are equal. Here is a partial design of this function:

  ; list=? : ...

  ; return #t iff the two lists are equal

  (check-expect (list=? '()            '()           string=?)  #t)

  (check-expect (list=? (list 1 2 3)    (list 1 2 3) =)         #t)

  (check-expect (list=? (list #t #f #t) (list #f #t) boolean=?) #f)

  (define (list=? l1 l2 is=?)

  (cond [(empty? l1) (empty? l2)]

  [(cons?  l1) (and ...

  ...)]))

  Think about what it means for two lists to be equal. Then fill in the places marked ... in the partial design above: the signature, and the rest of the and expression. Note that and can take any number of arguments.

• Converting a [List-of Boolean] to a BitString and back should result in the original list of Booleans. Design a function test-double-conv to test that conjecture, as follows. The function takes a list of Booleans as input, converts it to a BitString and back, and compares the result to the original list of Booleans, using list=?. It returns the Boolean value of this comparison (#t if equal, #f otherwise).

  Show at least three check-expects involving test-double-conv.

Exercise 2 In this exercise, do not use map, filter, or foldl/r.

• Design a function word-counts. It takes as input a "text", represented as a [List-of String]; you can think of each string as a word of the text. The function calculates, for each word, the frequency with which it occurs in the text. Your function should return this information in the form of a list of numbers, where the ith number is the frequency count of the ith word in the text. For example, if the input text is the list,

  (list "I" "really" "really" "don't" "know")

  then your function should return the same-length list (list 1 2 2 1 1). Note that the count corresponding to word "really", which occurs twice in the text, is reported twice.

  Hint: You will need a helper function that takes two lists of strings as input: one containing the words to count, and one containing the text in which to count the words. Initially these two lists are the same, namely the given text.

• Design a function char-counts. It takes as input a string and calculates, for each character in the string, the frequency with which it occurs in the string. Your function should return this information in the form of a list of numbers, where the ith number is the frequency count of the ith character in the string. For example, if the input is the word "really", your output should be the list (list 1 1 1 2 2 1).

  Hint: do not reinvent the wheel. This function is very short if you reuse functions you have designed or used in this homework before.

• Now let us go back to lists as input (instead of strings as in b.) and generalize the problem from a. Design a function counts. It takes as input a [List-of X] and calculates, for each element (of type X) in the list, the frequency with which it occurs in the list. Your function should return this information in the form of a list of numbers, where the ith number is the frequency count of the ith element in the list. For example, if the input is the list (list 1 2 3 2 1), your output should be the same-length list (list 2 2 1 2 2).

  But wait – there is a problem. To count the number of occurrences of an element in a list, we need to be able to compare list elements to a given element. This comparison function depends on what kinds of elements are in the list, i.e., it depends on X. For instance, for strings we may use string=?.

  Solve this problem by designing your function counts to have two arguments: lox to represent the list, and is=? to represent the comparison function.

  Hint: This part requires several functions with parametric signatures (i.e., signatures involving at least one type parameter, like (X)). Think about the signatures of these functions carefully.