CS1101S Studio S11 (T08C)

Streams II

Question 1

Describe the streams A and B produced by the following definitions. Assume that integers is the stream of positive integers (starting from 1):

function scale_stream(c, stream) {
    return stream_map(x => c * x, stream);
}

const A = pair(1, () => scale_stream(2, A));

function mul_streams(a,b) {
    return pair(head(a) * head(b),
                () => mul_streams(stream_tail(a), stream_tail(b)));
}

const B = pair(1, () => mul_streams(B, integers));

Question 2

To get some initial practice with streams, write definitions for each of the following:

• alt_ones: the stream 1, -1, 1, -1, … in as many ways as you can think of.
• zeroes: the infinite stream of 0's. Do this using alt_ones in as many ways as you can think of.

Now, show how to define the series:

$$\begin{array}{rl}{S}_1& =1+x+x^2+x^3+\cdots \\ S_2& =1+2x+3x^2+4x^3+\cdots \end{array}$$

const alt_ones = pair(1,()=>stream_map(x => -1*x,alt_ones));

function alt_ones() {
    return pair(1, ()=> pair(-1, alt_ones));
}

const zeros1 = scale_stream(0, alt_ones);
const zeros2 = stream_map(x => 0, alt_ones);
const zeros3 = subtract_series(alt_ones, alt_ones);

const zeros4 = add_streams(alt_ones, stream_tail(alt_ones)));

const S1 = ones;

const S1 = pair(1, ()=> S1);

function s1() {
    return pair(1, s1);
}

const S2 = pair(1, ()=>stream_map(x => x + 1,S2));
const S2 = integers_from(1);

const s2 = fun_to_series(x=>x+1);


function s2() {
    function helper(i) {
        return pair(i, ()=>helper(i+1));
    }
    return helper(1);
}

const s2 = pair(1, ()=> add_stream(s2, ones));

Bonus Round

Question 1

Given a stream s the following function returns a stream of pairs of elements from s:

function stream_pairs(s) {
    return is_null(s)
        ? null
        : stream_append(
            stream_map(
                sn => pair(head(s), sn),
                stream_tail(s)),
            stream_pairs(stream_tail(s)));
}

Suppose that ints is the (finite) stream 1, 2, 3, 4, 5. What is stream_pairs(ints)

Give the clearest explanation you can of how stream_pairs works.

Suppose that integers is the infinite stream of positive integers. What is the result of evaluating

const s2 = stream_pairs(integers);

Hint: Note the function stream_append is defined Source S3 as follows:

function stream_append(xs, ys) {
    return is_null(xs)
        ? ys
        : pair(head(xs),
               () => stream_append(stream_tail(xs),
                                   ys))
}

Consider the following variant of stream_append, called stream_append_pickle and the function stream_pairs2 which makes use of it.

function stream_append_pickle(xs, ys) {
    return is_null(xs)
        ? ys()
        : pair(head(xs),
               () => stream_append_pickle(stream_tail(xs),
                                          ys));
}

function stream_pairs2(s) {
    return is_null(s)
        ? null
        : stream_append_pickle(
            stream_map(
                sn => pair(head(s), sn),
                stream_tail(s)),
            () => stream_pairs2(stream_tail(s)));
}

const s2 = stream_pairs2(integers);

Why does the function stream_pair2 solve the problem that arose in the previous question?

What are the first few elements of stream_pairs2(integers)? Can you suggest a modification of stream_pairs2 that would be more appropriate in dealing with infinite streams?

Question 2