SICP Exercise 3.66 infinite streams of pairs

Exercise 3.66.  Examine the stream (pairs integers integers). Can you make any general comments about the order in which the pairs are placed into the stream? For example, about how many pairs precede the pair (1,100)? the pair (99,100)? the pair (100,100)? (If you can make precise mathematical statements here, all the better. But feel free to give more qualitative answers if you find yourself getting bogged down.)

 SOLUTION

 The pairs produced by (pairs integers integers) will look like this:

 (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) (1, 6) (1, 7) (1, 8) (1, 9)  (1, 10)  (1, 11) (1, 12) ...
         (2, 2) (2, 3) (2, 4) (2, 5) (2, 6) (2, 7) (2, 8) (2, 9)  (2, 10)  (2, 11) (2, 12) ...
                  (3, 3) (3, 4) (3, 5) (3, 6) (3, 7) (3, 8) (3, 9)  (3, 10)  (3, 11) (3, 12) ...
                           (4, 4) (4, 5) (4, 6) (4, 7) (4, 8) (4, 9)  (4, 10)  (4, 11) (4, 12) ...
                                    (5, 5) (5, 6) (5, 7) (5, 8) (5, 9)  (5, 10)  (5, 11) (5, 12) ...
                                             (6, 6) (6, 7) (6, 8) (6, 9)  (6, 10)  (6, 11) (6, 12) ...
                                                      (7, 7) (7, 8) (7, 9)  (7, 10)  (7, 11) (7, 12) ...
                                                               (8, 8) (8, 9)  (8, 10)  (8, 11) (8, 12) ...
                                                                        (9, 9)  (9, 10)  (9, 11) (9, 12) ...
                                                                                  (10, 10) (10, 11) (10, 12) ...
                                                                                               (11, 11) (11, 12) ...
                                                                                                            (12, 12) ...

 The recursive calls to 'pairs' and 'interleave' will generate pairs as follows:
(pairs indented for readability)

 1 (1, 1)
2 (1, 2)
3 (2, 2)
4 (1, 3)
5 (2, 3)
6 (1, 4)
7 (3, 3)
8 (1, 5)
9 (2, 4)
10 (1, 6)
11 (3, 4)
12 (1, 7)
13 (2, 5)
14 (1, 8)
15 (4, 4)
16 (1, 9)
17 (2, 6)
18 (1, 10)
19 (3, 5)
20 (1, 11)
21 (2, 7)
22 (1, 12)
23 (4, 5)
24 (1, 13)
25 (2, 8)
26 (1, 14)
27 (3, 6)
28 (1, 15)
29 (2, 9)
30 (1, 16)
31 (5, 5)
32 (1, 17)
33 (2, 10)
34 (1, 18)
35 (3, 7)
36 (1, 19)
37 (2, 11)
38 (1, 20)
39 (4, 6)
40 (1, 21)
41 (2, 12)
42 (1, 22)
43 (3, 8)
44
... and so on

 Note that for all (m, n), m <= n

 Position of (m, m)
(1, 1) —> 1
(2, 2) —> 1 + 2^1 = 3
(3, 3) —> 3 + 2^2 = 7
(4, 4) —> 7 + 2^3 = 15
(5, 5) —> 15 + 2^4 = 31
(m, m) —> (2^m) - 1

 Gap between pairs (m, n) and (m, n+1) is:
2^m for n > m
2^(m - 1) for n = m

 So the position of (m, n) would be:

 (2^m) - 1 when m = n
{(2^m) - 1}  + 2^(m - 1) when n = m + 1
{(2^m) - 1}  + 2^(m - 1) + (2^m) * (n - m -1) when n > m + 1

 Using the formula above, the position of (1, 100) would be:
{(2^1) - 1}  + 2^(1 - 1) + (2^1) * (100 - 1 - 1)
= 1 + 1 + 2 * 98
= 198

 The position of (99, 100) would be:
{(2^99) - 1}  + 2^(99 - 1)
= 2^99 + 2^98 - 1

 The position of (100, 100) would be:
(2^100) - 1

The code and tests are here.

Comments

Post a Comment

Popular posts from this blog

SICP Exercise 4.18 a alternative strategy for interpreting internal definitions

Exercise 4.18.   Consider an alternative strategy for scanning out definitions that translates the example in the text to (lambda < vars >   (let ((u '*unassigned*)         (v '*unassigned*))     (let ((a < e1 >)           (b < e2 >))       (set! u a)       (set! v b))     < e3 >)) Here  a  and  b  are meant to represent new variable names, created by the interpreter, that do not appear in the user's program. Consider the  solve  procedure from section  3.5.4 : (define (solve f y0 dt)   (define y (integral (delay dy) y0 dt))   (define dy (stream-map f y))   y) Will this ...
Read more

SICP Exercise 3.11 make-account internal definitions with local state

Image
Exercise 3.11.    In section  3.2.3  we saw how the environment model described the behavior of procedures with local state. Now we have seen how internal definitions work. A typical message-passing procedure contains both of these aspects. Consider the bank account procedure of section  3.1.1 : (define (make-account balance)   (define (withdraw amount)     (if (>= balance amount)         (begin (set! balance (- balance amount))                balance)         "Insufficient funds"))   (define (deposit amount)     (set! balance (+ balance amount))     balance)   (define (dispatch m)     (cond...
Read more

SICP Exercise 3.13 make-cycle

Image
Exercise 3.13.    Consider the following  make-cycle  procedure, which uses the  last-pair  procedure defined in exercise  3.12 : (define (make-cycle x)   (set-cdr! (last-pair x) x)   x) Draw a box-and-pointer diagram that shows the structure  z  created by (define z (make-cycle (list 'a 'b 'c))) What happens if we try to compute  (last-pair z) ? SOLUTION The code is here: Exercise 3.13 make-cycle The box-and-pointer diagrams are here:
Read more