Homework 9:
Due by 11:59pm on Thursday, November 21
Instructions
Download hw09.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. This homework is out of 2 points.
Tail Recursion
Q1: Replicate
Below is an implementation of the replicate
function, which was seen
in discussion. replicate
takes in an element x
and an integer n
,
and returns a list with x
repeated n
times.
(define (replicate x n)
(if (= n 0)
nil
(cons x (replicate x (- n 1)))))
Update this implementation of replicate
to be tail recursive. It should have
identical functionality to the non-tail recursive version.
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.
We test that your solution is tail recursive by calling
replicate
with a very large input. If your solution is not tail recursive and does not use a constant number of frames, it will not be able to successfully run.You may wish to use the built-in append procedure in your solution.
(define (replicate x n)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q replicate
Q2: 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
Q3: 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 your implementation for accumulate in the previous question is already
tail recursive, you may simply copy over that solution (replacing accumulate
with accumulate-tail
as appropriate).
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.
We test that your solution is tail recursive by calling
accumulate-tail
with a very large input. If your solution is not tail recursive and does not use a constant number of frames, it will not be able to successfully run.
(define (accumulate-tail combiner start n term)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q accumulate-tail
Streams
Q4: Multiples of 3
Define implicitly an infinite stream multiples-of-three
that contains
the multiples of 3.
You may use the map-stream
function defined below. map-stream
takes in
a one-argument function f
and a stream s
and returns a new stream containing
the elements of s
with f
applied.
(define (map-stream f s)
(if (null? s)
nil
(cons-stream (f (car s)) (map-stream f (cdr-stream s)))))
Do not define any other helper functions.
(define (map-stream f s)
(if (null? s)
nil
(cons-stream (f (car s)) (map-stream f (cdr-stream s)))))
(define multiples-of-three
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q multiples_3
Q5: NondecreaStream
Define a function nondecreastream
, which takes in a stream of numbers and outputs
a stream of lists, which overall has the same numbers in the same order, but grouped
into segments that are non-decreasing.
For example, if the input is a stream containing elements
1 2 3 4 1 2 3 4 1 1 1 2 1 1 0 4 3 2 1 ...
the output should contain elements
(1 2 3 4) (1 2 3 4) (1 1 1 2) (1 1) (0 4) (3) (2) (1) ...
If the input is an infinite stream, the output should be an infinite stream and if the input is finite, the output should also be finite. Even if the input is an infinite stream, you can assume that every non-decreasing segment is finite.
Hint: avoid any direct recursive calls outside the context of a second part of a call to
cons-stream
, otherwise your solution won't work for infinite streams!
(define (nondecreastream s)
'YOUR-CODE-HERE)
Use Ok to test your code:
python3 ok -q nondecreastream