Homework 3 is due Tuesday, April 27, 2021 at 11:59pm (Chicago Time)

Preliminaries

You will submit your work in a file called hw3.rkt, which should be located in a directory called hw3 in your repository. You will need to create the directory and file on your machine and then add, commit, and push it to GitLab. Be careful to get the directory and file names right.

To get started, make sure that your local repository is up to date.

cd cs151
git pull

assuming that cs151 is the name of your local repository.

The following shell commands, will get you started. Note the second command (the touch) creates an empty file in the hw3 directory and the third command adds the hw3 directory, which includes the hw3.rkt file (so it will be added too).

mkdir hw3
touch hw3/hw3.rkt
git add hw3
git commit -m "getting ready for homework 3"
git push

At this point, you have added, committed, and pushed an empty file named hw3.rkt and the hw3 directory to your repository on the server. It is important that this file has exactly this name and location, since we will be looking for your work under this name at collection time.

Open the hw3.rkt file in DrRacket. Once you have opened your hw3.rkt file with DrRacket, go to the Language menu, then select Choose Language…​, and then choose "Determine language from source" from the popup menu on the lower left edge of the application window.

Adding boilerplate

The first step is to add the standard comments, require directives, and testing command to the file. Copy the following code into the file and save it.

#lang typed/racket

;; CMSC15100 Spring 2021
;; Homework 3
;; <YOUR NAME HERE>

;; include CS151-specific definitions
(require "../include/cs151-core.rkt")

;; include testing framework
(require typed/test-engine/racket-tests)

;; YOUR CODE HERE

;; run tests
;;
(test)

You should replace "<YOUR NAME HERE>" with your name and your solution to the questions below should replace the

;; YOUR CODE HERE

comment.

Homework Problems

For every function you write, you must preface the function definition with a type signature and a purpose comment. You must also follow the function with tests with check testers (check-expect, check-within, etc.). Write helper functions where it seems like a good idea to do so. All functions need contracts, purposes and tests, even if they are "only" helper functions.

Problem 1

This problem involves writing a number of simple recursive functions over lists.

Note

Your solution should not use any of the list functions provided by Typed Racket, other than cons, first, rest, and empty?. You may, however, use a function defined in this problem to implement another function in the problem.

fifths : (Listof Exact-Rational) -> (Listof Exact-Rational)

divide all numbers in the list by five.

scale-list : Real (Listof Real) -> (Listof Real)

multiply the first argument to each element of the second argument.

> (scale-list 7 '(1 2 3))
'(7 14 21)

negatives : (Listof Integer) -> (Listof Integer)

filter out any non-negative numbers in the list

> (negatives '(0 -1 1 0 -3))
'( -1 -3)

replicate : (All (A) (Integer A -> (Listof A)))

takes a length n and a value v, and returns a list of length n where every element in the list is v. For example,

> (replicate 4 "hello")
'("hello" "hello" "hello" "hello")

If n is less-than or equal to zero, then return the empty list.

list-sum : (Listof Number) -> Number

compute the sum of the numbers in the list.

exactly-one : (Listof Boolean) -> Boolean

should return true if exactly one item in the list is true and false otherwise. Furthermore, your solution should terminate as soon as it sees more than one true item.

that-many : (Listof Integer) -> (Listof (Listof Integer))

build a list of lists containing "that many" of each; for example,

> (that-many '(2 1 3))
'((2 2) (1) (3 3 3))

You should use the empty list for negative values; for example,

> (that-many '(-2 1 3))
'(() (1) (3 3 3))

drop : (All (A) (Listof A) Integer -> (Listof A))

given a list xs and an integer n, this function returns the list that remains after discarding the first n elements. If n is less than zero then it returns xs and if n is greater than the length of xs it returns the empty list.

Problem 2

We can represent a natural number \(n\) as a sequence of \(k\) binary digits (bits) \(b_0, b_1, \ldots, b_{k-1}\), where \(n = \sum_{i=0}^{k-1} b_i 2^{i}\). We can represent such a bit sequence as a (Listof Boolean), where we use #f for 0 and #t for 1 and the first element of the list corresponds to \(b_0\). For example, \(19 = 2^0 + 2^1 + 2^4\), which corresponds to the list (list #t #t #f #f #t).

Copy the following code into your hw3.rkt file:

;; PROBLEM 2

;; a representation of natural numbers as a sequence of bits; least-significant
;; bit first.
(define-type Nat-Bits (Listof Boolean))

For the functions below, you do not need reverse or length to implement them.

is-valid-num?

A Nat-Bits value is said to be valid if the last bit in the list is #t (a #f or zero-bit in the last position does not add information). Note that with this restriction, zero is represented as the empty list of bits.

Write a function that tests if a Nat-Bits value is valid and returns #t if it is and #f if it is not valid.

bits->natural

Write a function bits->natural that converts a Nat-Bits value to its equivalent Natural value.

Tip

Consider a four digit number \(b_0 \, b_1 \, b_2 \, b_3\). The sum \(b_0 2^0 + b_1 2^1 + b_2 2^2 + b_3 * 2^3\) can be computed as \(b_0 + 2 (b_1 + 2 (b_2 + 2 (b_3)))\).

add

Write a function add that takes two Nat-Bits values as arguments and returns their sum as a Nat-Bits value. Your solution should work directly on the Nat-Bits representation (i.e., solutions that convert to a Natural and back will not be accepted). The result should be a valid Nat-Bits value.

Tip

Recall the method that you learned to do multi-digit addition in grade school using carries. You will need a recursive helper function that takes a carry in and propagates a carry out to implement addition. You may find it useful to write a second helper function that propagates a carry of one (i.e., think about what happens for (add (list #t) (list #t #t #t))).

greater

Write a function greater that takes two Nat-Bits values as arguments and returns #t if the first argument is greater than the second, and #f otherwise. Your solution should work directly on the Nat-Bits representation (i.e., solutions that convert to a Natural will not be accepted).

Submission Instructions

Your solution to the assignment must be pushed to the GitLab server by Tuesday, April 27, 2021; we do not accept late work. Remember that to submit your work you will have to add and commit it to your local repository, and then push your changes to the server. You can verify that your work has been submitted by using the web interface to the server.

We strongly recommend pushing your code after you write and test each function; do not wait to the last minute to discover that you cannot commit your work for some reason!! Only your last commit before the deadline will be evaluated by your graders. Note, however, that you should not submit code that has syntax or type errors in it. If you cannot figure out how to fix a particular type error, comment out the offending code and include a note for the grader.

For the present, do not worry about functions being passed bogus inputs, e.g., a negative income. We will deal with erroneous arguments to functions later in the quarter.