Mini-project about implementing a sieve

The motivation for this mini-project is the property that successively adding the successive odd numbers to 0 yields squares:

• 0 + 1 = 1 = 1^2
• 0 + 1 + 3 = 4 = 2^2
• 0 + 1 + 3 + 5 = 9 = 3^2
• 0 + 1 + 3 + 5 + 7 = 16 = 4^2
• etc.

This property suggests that we can map the stream of positive odd numbers to the stream of squares using a function that, given a stream, maps it to the stream of its partial sums. Question 2 is dedicated to implementing this function in OCaml.

As for the stream of positive odd numbers, it can be obtained by filtering out all the second elements out of the stream of positive natural numbers. Question 1 is dedicated to implementing this function in OCaml.

The stream of positive natural numbers itself is obtained as the stream of partial sums of the constant stream that only contains 1, which itself is obtained as the stream of partial sums of the stream that starts with 1 and forever continues with 0.

Food for thought:

• In your unit tests, you will have much use of the OCaml function that maps the prefix of a stream to an OCaml list.

Question 1

Implement an OCaml function strike_out that, given a stream and a non-negative integer n, constructs a stream where each n+2th element of the given stream is struck out.

Examples:

1. Given the stream of natural numbers (i.e., 0, 1, 2, 3, etc.) and the number 0, this OCaml function strikes out every second element of this stream and constructs the stream of even natural numbers (i.e., 0, 2, 4, 6, 8, etc.).
2. Given the stream of positive natural numbers (i.e., 1, 2, 3, 4, etc.) and the number 0, this OCaml function strikes out every second element of this stream and constructs the stream of odd natural numbers (i.e., 1, 3, 5, 7, etc.).
3. Given the stream of natural numbers (i.e., 0, 1, 2, 3, etc.) and the number 1, this OCaml function strikes out every third element of this stream and constructs the stream consisting of 0, 1, 3, 4, 6, 7, 9, etc.
4. Given the stream of positive natural numbers (i.e., 1, 2, 3, 4, etc.) and the number 1, this OCaml function strikes out every third element of this stream and constructs the stream consisting of 1, 2, 4, 5, 7, 8, 10, etc.).
5. Given the stream of natural numbers (i.e., 0, 1, 2, 3, 4, etc.) and the number 2, this OCaml function strikes out every fourth element of this stream and constructs the stream consisting of 0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, etc.
6. Given the stream of positive natural numbers (i.e., 1, 2, 3, 4, etc.) and the number 2, this OCaml function strikes out every fourth element of this stream and constructs the stream consisting of 1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, etc.

Question 2

Implement an OCaml function scan that, given a stream of integers, constructs the stream of the partial sums of the given stream. In other words, given a stream of values v0, v1, v2, v3, etc., this OCaml function constructs the stream of values v0, v0 + v1, v0 + v1 + v2, v0 + v1 + v2 + v3, etc.

Examples:

1. Given the stream of consecutive 1’s and -1’s (i.e., 1, -1, 1, -1, 1, -1, etc.), this OCaml function constructs the stream of consecutive 1’s and 0’s (i.e., 1, 0, 1, 0, 1, 0, etc.).
2. Given the stream that starts with 1 and then continues with 0’s (i.e., 1, 0, 0, 0, etc.), this OCaml function constructs the stream of 1’s (i.e., 1, 1, 1, 1, etc.).
3. Given the stream of 1’s (i.e., 1, 1, 1, 1, etc.), this OCaml function constructs the stream of positive natural numbers (i.e., 1, 2, 3, 4, etc.).
4. Given the stream of odd natural numbers (i.e., 1, 3, 5, 7, etc.), this OCaml function constructs the stream of successive squares (i.e., 1, 4, 9, 16, 25, etc.).

Hint: use an accumulator.

Extra points for imaginative examples in your unit-test function.

Question 3 (very, very simple)

Implement an OCaml function composite that is the composition of the first OCaml function above (i.e., strike_out, the one that strikes out numbers) and the second OCaml function above (i.e., scan, the one that computes partial sums). Given a stream and a natural number n, this composite function

• first strikes out every n+2th element of the given stream, resulting in an intermediate stream, and then
• constructs the stream of the partial sums of this intermediate stream.

Question 4

Implement a sieve as an OCaml function that, given an initial stream s and a rank k (a non-negative integer),

• applies the composite function above to the given stream s and k, resulting in a new stream,
• applies the composite function above to the new stream and k-1, resulting in a new new stream,
• applies the composite function above to the new new stream and k-2, resulting in a new new new stream,

and keeps doing that until the second argument is 0.

Concretely:

0. given s_init and 0, the sieve yields the result of evaluating composite s_init 0;
1. given s_init and 1, the sieve yields the result of evaluating composite (composite s_init 1) 0;
2. given s_init and 2, the sieve yields the result of evaluating composite (composite (composite s_init 2) 1) 0;
3. given s_init and 3, the sieve yields the result of evaluating composite (composite (composite (composite s_init 3) 2) 1) 0;
4. etc.

Characterize this resulting stream in term of the given non-negative integer when the initial stream starts with 1 and continues with 0’s (i.e., 1, 0, 0, 0, etc.).

Concretize this characterization with a unit-test function.

Extra points for also expressing the sieve with a fold function over natural numbers.

Question 5 (optional)

1. What is the result of your sieve if the initial stream, instead of starting with 1 and continuing with 0’s, starts with 1 and continues with 1’s (i.e., 1, 1, 1, 1, etc.)?
2. What is the result of your sieve if the initial stream starts with 1 and continues with 2, 3, 4, 5, etc., i.e., if it the initial stream is the increasing stream of positive integers?
3. What is the result of your sieve if the initial stream starts with 1 and continues with 4, 9, 16, 25, etc., i.e., if it the initial stream is the increasing stream of positive squares?

Question 6 (optional)

What is the result of your sieve if instead of starting with 1 and continuing with 0’s, the initial stream starts with 10 and continues with 0’s (i.e., 10, 0, 0, 0, etc.)? What if it starts with 2? What if it starts with 100?

Question 7 (optional)

What is the result of your sieve if instead of starting with 1 and continuing with 0’s, the initial stream starts with 1 continues with 2’s (i.e., 1, 2, 2, 2, etc.)? What if it starts with 1 and continues with 10’s? What if it starts with 1 and continues with 100’s?

Question 8 (optional)

Generalize Questions 6 and 7.

Resources

• The OCaml code for the present lecture note (latest version: 04 Apr 2020).

Version

Created [04 Apr 2020]