Homework 9:

Due by 11:59pm on Thursday, November 21

Instructions

Download hw09.zip.

Our course uses a custom version of Scheme (which you will build for Project 4) included in the starter ZIP archive. To start the interpreter, type python3 scheme. To run a Scheme program interactively, type python3 scheme -i <file.scm>. To exit the Scheme interpreter, type (exit).

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:

Grading: Homework is graded based on effort, not correctness. However, there is no partial credit; you must show substantial effort on every problem to receive any points. This homework is out of 2 points.

Tail Recursion

Q1: Replicate

Below is an implementation of the replicate function, which was seen in discussion. replicate takes in an element x and an integer n, and returns a list with x repeated n times.

(define (replicate x n)
	(if (= n 0)
		nil
		(cons x (replicate x (- n 1)))))

Update this implementation of replicate to be tail recursive. It should have identical functionality to the non-tail recursive version.

If you're running into an recursion depth exceeded error and you're using the staff interpreter, it's very likely your solution is not properly tail recursive.

We test that your solution is tail recursive by calling replicate with a very large input. If your solution is not tail recursive and does not use a constant number of frames, it will not be able to successfully run.

You may wish to use the built-in append procedure in your solution.

(define (replicate x n)
  'YOUR-CODE-HERE
  )

Use Ok to test your code:

python3 ok -q replicate

Q2: Accumulate

Fill in the definition for the procedure accumulate, which combines the first n natural numbers according to the following parameters:

  1. combiner: a function of two arguments
  2. start: a number with which to start combining
  3. n: the number of natural numbers to combine
  4. term: a function of one argument that computes the nth term of a sequence

For example, we can find the product of all the numbers from 1 to 5 by using the multiplication operator as the combiner, and starting our product at 1:

scm> (define (identity x) x)
scm> (accumulate * 1 5 identity)  ; 1 * 1 * 2 * 3 * 4 * 5
120

We can also find the sum of the squares of the same numbers by using the addition operator as the combiner and square as the term:

scm> (define (square x) (* x x))
scm> (accumulate + 0 5 square)  ; 0 + 1^2 + 2^2 + 3^2 + 4^2 + 5^2
55
scm> (accumulate + 5 5 square)  ; 5 + 1^2 + 2^2 + 3^2 + 4^2 + 5^2
60

You may assume that the combiner will always be commutative: i.e. the order of arguments do not matter.

(define (accumulate combiner start n term)
  'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q accumulate

Q3: Tail Recursive Accumulate

Update your implementation of accumulate to be tail recursive. It should still pass all the tests for "regular" accumulate!

You may assume that the input combiner and term procedures are properly tail recursive.

If your implementation for accumulate in the previous question is already tail recursive, you may simply copy over that solution (replacing accumulate with accumulate-tail as appropriate).

If you're running into an recursion depth exceeded error and you're using the staff interpreter, it's very likely your solution is not properly tail recursive.

We test that your solution is tail recursive by calling accumulate-tail with a very large input. If your solution is not tail recursive and does not use a constant number of frames, it will not be able to successfully run.

(define (accumulate-tail combiner start n term)
  'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q accumulate-tail

Streams

Q4: Multiples of 3

Define implicitly an infinite stream multiples-of-three that contains the multiples of 3.

You may use the map-stream function defined below. map-stream takes in a one-argument function f and a stream s and returns a new stream containing the elements of s with f applied.

(define (map-stream f s)
	(if (null? s)
		nil
		(cons-stream (f (car s)) (map-stream f (cdr-stream s)))))

Do not define any other helper functions.

(define (map-stream f s)
    (if (null? s)
    	nil
    	(cons-stream (f (car s)) (map-stream f (cdr-stream s)))))

(define multiples-of-three
  'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q multiples_3

Q5: NondecreaStream

Define a function nondecreastream, which takes in a stream of numbers and outputs a stream of lists, which overall has the same numbers in the same order, but grouped into segments that are non-decreasing.

For example, if the input is a stream containing elements

1 2 3 4 1 2 3 4 1 1 1 2 1 1 0 4 3 2 1 ...

the output should contain elements

(1 2 3 4) (1 2 3 4) (1 1 1 2) (1 1) (0 4) (3) (2) (1) ...

If the input is an infinite stream, the output should be an infinite stream and if the input is finite, the output should also be finite. Even if the input is an infinite stream, you can assume that every non-decreasing segment is finite.

Hint: avoid any direct recursive calls outside the context of a second part of a call to cons-stream, otherwise your solution won't work for infinite streams!

(define (nondecreastream s)
    'YOUR-CODE-HERE)

Use Ok to test your code:

python3 ok -q nondecreastream