Homework 12
Due by 11:59pm on Tuesday, 11/15
Instructions
Download hw12.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:
Homework Questions
Question 1: 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
Question 2: 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
.
(define (scale-stream s k)
'YOUR-CODE-HERE
)
Use OK to test your code:
python3 ok -q scale-stream
Question 3: 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. 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