# Homework 10: hw10.zip

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

## Instructions

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
120``````

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
55
scm> (accumulate + 5 5 square)  ; 5 + 1^2 + 2^2 + 3^2 + 4^2 + 5^2
60``````

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)
'YOUR-CODE-HERE
)``````

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)
'YOUR-CODE-HERE
)``````

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)
'YOUR-CODE-HERE
(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))))
s
scm> (define encoding (rle s))
encoding
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)
'YOUR-CODE-HERE
)``````

Use Ok to test your code:

``python3 ok -q rle``