# Homework 10 Solutions

## Solution Files

### 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)
(if (= n 0)
start
(accumulate combiner (combiner (term n) start) (- n 1) 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)
(define (accum-helper x so-far)
(if (= x 0)
so-far
(accum-helper (- x 1) (combiner (term x)))
))
(accum-helper n start))
; ALT solution
(define (accumulate-tail combiner start n term)
(if (= n 0)
start
(accumulate-tail combiner (combiner (term n) start) (- n 1) term)))
```

Use Ok to test your code:

`python3 ok -q accumulate-tail`

If we were to implement this iteratively in Python, it might look something like:

```
def accumulate(combiner, start, n, term):
total = start
while n > 0:
total = combiner(total, term(n))
n -= 1
return total
```

With that in mind, we can create a helper function in Scheme to help us track a running total. This will be updated in each recursive call.

The alternative solution simply uses the `start`

value to track all the
values we've used so far, but it effectively functions the same.

### 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)
(define (helper sum-so-far stream-remaining)
(if (null? stream-remaining)
nil
(begin (define new-sum (+ sum-so-far (car stream-remaining)))
(cons-stream new-sum (helper new-sum (cdr-stream stream-remaining)))))) (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)
(define (track-run elem st len)
(cond ((null? st) (cons-stream (list elem len) nil))
((= elem (car st)) (track-run elem (cdr-stream st) (+ len 1)))
(else (cons-stream (list elem len) (rle st))))
)
(if (null? s)
nil
(track-run (car s) (cdr-stream s) 1)))
```

Use Ok to test your code:

`python3 ok -q rle`