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

## Instructions

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