Homework 11
Due by 11:59pm on Thursday, 4/19
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. The
predicate is a one argument function that returns either #t
for a match
or #f
otherwise. 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
multiplied by k
. For example, if k
is 2, then all the
elements in the stream are doubled. 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.
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:
We don't directly test if your solution uses constant space, but it will likely timeout if you do not use constant space.
(define (has-cycle-constant s)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q has-cycle-constant