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

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