# Homework 10

*Due by 11:59pm on Friday, 8/7*

## Instructions

Download hw10.zip. Inside the archive, you will find a file called hw10.scm, along with a copy of the OK autograder.

**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. See Lab 1 for 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:

## Required questions

### Question 1: Filter

Write a function `filter`

, which takes in a predicate and a Scheme list and
returns a Scheme list whose elements are the elements from the inputted Scheme
list that satisfy the predicate.

**Make sure filter is tail recursive!**

Hint: Try writing the function iteratively in Python, then convert into a tail recursive Scheme function.You will also find the built-in

`append`

function useful.`append`

concatenates two Scheme lists, much like the`+`

operator in Python.

```
(define (filter pred lst)
'YOUR-CODE-HERE
)
```

Use OK to unlock and test your code:

```
python3 ok -q filter -u
python3 ok -q filter
```

This question uses the following tail-recursive version of `int-list`

(which
creates a list of integers from 1 to `n`

) and `equal?`

(which checks if two
lists `s0`

and `s1`

contain the same elements):

```
(define (int-list n total)
(if (= n 0)
total
(int-list (- n 1) (cons n total))))
(define (equal? s0 s1)
(cond ((and (null? s0) (null? s1)) True)
((or (null? s0) (null? s1)) False)
(else (and (= (car s0) (car s1))
(equal? (cdr s0) (cdr s1))))))
```

### Stream utilities

For the following questions use the functions `integers`

and `stream-to-list`

in
their tests:

```
(define (integers first)
(cons-stream first (integers (+ first 1))))
(define (stream-to-list s num-elements)
(if (or (null? s) (= num-elements 0))
nil
(cons (car s) (stream-to-list (stream-cdr s) (- num-elements 1)))))
```

### Question 2

Implement the function `scale-stream`

, which returns a stream over each
element of an input stream, scaled by `k`

:

```
(define (scale-stream s k)
'YOUR-CODE-HERE
)
```

Use OK to test your code:

`python3 ok -q scale-stream`

### Question 3

Implement `merge`

, which takes two streams `s1`

and `s2`

whose elements are
ordered. `merge`

returns a stream that contains elements from `s1`

and
`s2`

in sorted order, elimnating repetition. You may assume `s0`

and `s1`

themselves do not contain repeats. `s1`

and `s2`

may or may not be infinite
streams.

```
(define (merge s0 s1)
(cond ((null? s0) s1)
((null? s1) s0)
; YOUR CODE HERE
))
```

Use OK to test your code:

`python3 ok -q merge`

### Question 4

A famous problem, first raised by Richard Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2, 3, or 5. These are called regular numbers. One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2, 3, and 5. But this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement.

As an alternative, we can write a function that returns an infinite stream of
such numbers. Let us call the stream of numbers `s`

and notice the following
facts about it.

`s`

begins with`1`

.- The elements of
`(scale-stream s 2)`

are also elements of`s`

. - The same is true for
`(scale-stream s 3)`

and`(scale-stream s 5)`

. - These are all of the elements of
`s`

.

Now all we have to do is combine elements from these sources. Use the `merge`

function you defined previously to fill in the definition of `make-s`

:

```
(define (make-s)
(cons-stream 1
'YOUR-CODE-HERE
))
```

Use OK to test your code:

`python3 ok -q make-s`