Homework 11
Due by 11:59pm on Tuesday, 11/14
Instructions
Download hw11.zip.
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:
Q1: Find
Define a function find
which takes in as input a stream and a predicate, and
returns the first element in the stream satisfying the predicate. If the item is
not found, return #f
(assume that a predicate will never match #f
).
Extra note: Is it always possible to correctly return
#f
? Can you think of a possible inputs
where we might run into issues (we won't test you on this case)?
(define (find s predicate)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q find
Q2: Scale Stream
Implement the function scale-stream
, which takes a stream s
and a number
k
, and returns a stream where each element is the corresponding element of s
scaled by k
. Your solution should work even if s
has an infinite number of
items.
(define (scale-stream s k)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q scale-stream
Q3: Cycles
In Scheme, it's possible to have a stream with cycles. That is, a stream may contain itself as part of the stream definition.
scm> (define s (cons-stream 1 (cons-stream 2 s)))
scm> (car s)
1
scm> (car (cdr-stream (cdr-stream s)))
1
Implement has-cycle
, that returns whether a stream contains a cycle.
Note: You may assume that the input is either a stream of some unknown finite length, or contains a cycle.
(define (has-cycle s)
'YOUR-CODE-HERE
)
Hint:
eq?
may be used to check if two items are the same stream instance.scm> (define s (cons-stream 1 s)) scm> (eq? s (cdr-stream s)) True
It may be helpful to keep track of already seen stream instances.
Use Ok to test your code:
python3 ok -q has-cycle
Extra question: This question is not worth extra credit and is entirely optional (i.e. there are no test cases that check if you use constant space). It is designed to challenge you to think creatively!
Implement has-cycle-constant
with only constant space. The solution is
short (fewer than 20 lines of code), but requires a clever idea. Try to discover
the solution yourself before asking around:
(define (has-cycle-constant s)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q has-cycle-constant