# Homework 9: hw09.zip

Due by 11:59pm on Thursday, November 21

## Instructions

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