pairs starts with ((car s) (car t)) and then interleaves

a) the stream formed by mapping ((car s) _) against (cdr t) i.e (1 _) (2 3 4 …) or (1 2) (1 3) (1 4) …

b) the stream formed by (pairs (cdr s) (cdr t))

The pair (1 n) is in position:

1 + 2(n-1) (1 1) + interleaved items from a) and b)

The number of pairs preceding (1 n) is therefore 2(n – 1) – 1 so (1 100) has 197 preceding pairs.

The first 20 pairs are:

(1 1)

(1 2)

(2 2)

(1 3)

(2 3)

(1 4)

(3 3)

(1 5)

(2 4)

(1 6)

(3 4)

(1 7)

(2 5)

(1 8)

(4 4)

(1 9)

(2 6)

(1 10)

(3 5)

(1 11)

The pair (x y) won’t come from the even numbered items in the result stream as they are all (1 n) so for now ignore those. The remaining items come from (pairs (2 3 4 …) (2 3 4 …))

(2 2)

(2 3)

(3 3)

(2 4)

(3 4)

(2 5)

(4 4)

(2 6)

(3 5)

In this stream (2 m) is in position

1+2(m-1) and so has 2(m-1) – 1 preceding pairs. These are interleaved with the (1 n) stream (which appear in every 2^{nd} position) which means (2 m) pairs have 2(2[m-1]-1) preceding pairs.

There is a pattern emerging:

(3 m) will have 2(m-1)-1 preceding items interleaved and so has about 4(2[m-1]-1) preceding items.

In general then pair (x y) has 2^{x-1}(2[y-1]-1) preceding items.

(1 100) : 2^{0}(2*99 – 1) = 197

(99 100) : 2^{98}(2*99 – 1) = 99 * 2^{99} – 2^{98}

(100 100) : 2^{99}(2*99 – 1) = 99 * 2^{99} – 2^{99}

I don’t have huge confidence in these values. I think it’s more accurate to say 2(…2(2(2(m-1)-1)-1)…-1 but these are probably close enough though.

[…] the same reason we used interleave instead of stream-append to generate pairs of integers in Exercise 3.66. The simple answer is to allow values from both streams to be displayed in if the first stream is […]