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, typepython3 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 argumentsstart
: a number with which to start combiningn
: the number of natural numbers to combineterm
: 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