Homework 10:

Due by 11:59pm on Thursday, 11/15


Download hw10.zip.

Our course uses a custom version of Scheme (which you will build for Project 4) included in the starter ZIP archive. To start the interpreter, type python3 scheme. To run a Scheme program interactively, type python3 scheme -i <file.scm>. To exit the Scheme interpreter, type (exit).

Submission: When you are done, submit with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on okpy.org. See Lab 0 for more instructions on submitting assignments.

Using Ok: If you have any questions about using Ok, please refer to this guide.

Readings: You might find the following references useful:

Grading: Homework is graded based on effort, not correctness. However, there is no partial credit; you must show substantial effort on every problem to receive any points.

Q1: Accumulate

Fill in the definition for the procedure accumulate, which combines the first n natural numbers according to the following parameters:

  1. combiner: a function of two arguments
  2. start: a number with which to start combining
  3. n: the number of natural numbers to combine
  4. term: a function of one argument that computes the nth term of a sequence

For example, we can find the product of all the numbers from 1 to 5 by using the multiplication operator as the combiner, and starting our product at 1:

scm> (define (identity x) x)
scm> (accumulate * 1 5 identity)  ; 1 * 1 * 2 * 3 * 4 * 5

We can also find the sum of the squares of the same numbers by using the addition operator as the combiner and square as the term:

scm> (define (square x) (* x x))
scm> (accumulate + 0 5 square)  ; 0 + 1^2 + 2^2 + 3^2 + 4^2 + 5^2
scm> (accumulate + 5 5 square)  ; 5 + 1^2 + 2^2 + 3^2 + 4^2 + 5^2

You may assume that the combiner will always be commutative: i.e. the order of arguments do not matter.

(define (accumulate combiner start n term)

Use Ok to test your code:

python3 ok -q accumulate

Q2: Tail Recursive Accumulate

Update your implementation of accumulate to be tail recursive. It should still pass all the tests for "regular" accumulate!

You may assume that the input combiner and term procedures are properly tail recursive.

If you're running into an recursion depth exceeded error and you're using the staff interpreter, it's very likely your solution is not properly tail recursive.

(define (accumulate-tail combiner start n term)

Use Ok to test your code:

python3 ok -q accumulate-tail

Q3: Partial sums

Define a function partial-sums, which takes in a stream with elements

a1, a2, a3, ...

and outputs the stream

a1, a1 + a2, a1 + a2 + a3, ...

If the input is a finite stream of length n, the output should be a finite stream of length n. If the input is an infinite stream, the output should also be an infinite stream.

(define (partial-sums stream)
  (helper 0 stream)

Use Ok to test your code:

python3 ok -q partial-sums

Q4: Run-Length Encoding

Run-length encoding is a very simple data compression technique, whereby runs of data are compressed and stored as a single value. A run is defined to be a contiguous sequence of the same number. For example, in the (finite) sequence

1, 1, 1, 1, 1, 6, 6, 6, 6, 2, 5, 5, 5

there are four runs: one each of 1, 6, 2, and 5. We can represent the same sequence as a sequence of two-element lists:

(1 5), (6 4), (2 1), (5 3)

Notice that the first element of each list is the number in a run, and the second element is the number of of times that number appears in the run.

We will extend this idea to streams. Write a function called rle that takes in a stream of data, and returns a corresponding stream of two-element lists, which represents the run-length encoded version of the stream. You do not have to consider compressing infinite runs.

scm> (define s (cons-stream 1 (cons-stream 1 (cons-stream 2 nil))))
scm> (define encoding (rle s))
scm> (car encoding)  ; Run of number 1 of length 2
(1 2)
scm> (car (cdr-stream encoding))  ; Run of number 2 of length 1
(2 1)
scm> (stream-to-list (rle (list-to-stream '(1 1 2 2 2 3))))  ; See functions in lab13.scm
((1 2) (2 3) (3 1))
(define (rle s)

Use Ok to test your code:

python3 ok -q rle