Due by 11:59pm on Tuesday, 11/15


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 input s where we might run into issues (we won't test you on this case)?

(define (find s predicate)

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)

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)
scm> (car (cdr-stream (cdr-stream s)))

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)

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))

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)

Use OK to test your code:

python3 ok -q has-cycle-constant