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:

  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)
(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))))
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)
(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