# Homework 10:

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

## Instructions

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:

`combiner`

: a function of two arguments`start`

: a number with which to start combining`n`

: the number of natural numbers to combine`term`

: a function of one argument that computes the*n*th 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`