SICP упражнение 3.67 - создание всех пар целых чисел без ограничений - PullRequest
Новая
       82

SICP упражнение 3.67 - создание всех пар целых чисел без ограничений

4 голосов
/ 19 марта 2019

Из SICP:

Это бесконечный поток единиц: 

 (define ones (cons-stream 1 ones))

Это бесконечный поток натуральных чисел: 

 ; add-streams takes two streams and produces a stream of their elementwise sum
 (define integers (cons-stream 1 (add-streams ones integers)))

interleaveполучает элементы поочередно из двух потоков и возвращает результат 

(define (interleave s1 s2)
  (if (stream-null? s1)
      s2
      (cons-stream 
       (stream-car s1)
       (interleave s2 (stream-cdr s1)))))

Следующая процедура pairs берет два потока s и t и создает все пары (s_i, t_j), такие что i <= j. 

(define (pairs s t)
  (cons-stream
   (list (stream-car s) (stream-car t))
   (interleave
    (stream-map (lambda (x) 
                  (list (stream-car s) x))
                (stream-cdr t))
    (pairs (stream-cdr s) (stream-cdr t)))))

Итак, 

 (pairs integers integers)

производит все пары целых чисел i и j с i <= j.

Вот упражнение 3.67:

Упражнение 3.67. Измените процедуру pairs, чтобы (pairs integers integers) создавал поток всех пар целых чисел (i, j) (без условия (i <= j)).Подсказка: вам нужно будет смешать в дополнительном потоке.

Мое решение: 

(define (pairs2 s t)
  (cons-stream
   (list (stream-car s) (stream-car t))
   (interleave
    (stream-map (lambda (x) 
                  (list (stream-car s) x))
                (stream-cdr t))
    (pairs2 (stream-cdr s) t))))

Итак, я только что изменил (stream-cdr t) на t в последней рекурсиивызов.Похоже, это приводит к получению всех пар целых чисел.

Что я не понимаю, так это утверждение:

Подсказка: вам нужно будет смешать дополнительный поток.

Что это значит?Мое решение неверно?Что они имеют в виду, когда говорят дополнительный поток?

Используя мою модифицированную процедуру pairs2, это первые 20 результатов: 

> (define p2 (pairs2 integers integers))
> (stream-ref p2 0)
(1 1)
> (stream-ref p2 1)
(1 2)
> (stream-ref p2 2)
(2 1)
> (stream-ref p2 3)
(1 3)
> (stream-ref p2 4)
(2 2)
> (stream-ref p2 5)
(1 4)
> (stream-ref p2 6)
(3 1)
> (stream-ref p2 7)
(1 5)
> (stream-ref p2 8)
(2 3)
> (stream-ref p2 9)
(1 6)
> (stream-ref p2 10)
(3 2)
> (stream-ref p2 11)
(1 7)
> (stream-ref p2 12)
(2 4)
> (stream-ref p2 13)
(1 8)
> (stream-ref p2 14)
(4 1)
> (stream-ref p2 15)
(1 9)
> (stream-ref p2 16)
(2 5)
> (stream-ref p2 17)
(1 10)
> (stream-ref p2 18)
(3 3)
> (stream-ref p2 19)
(1 11)

1 Ответ

3 голосов
/ 19 марта 2019

Похоже, ваш ответ действительно правильный.Для чего стоит, я смог решить это, используя один дополнительный поток, который авторы имели в виду с подсказкой «Вам нужно будет смешать в дополнительном потоке»: 

(define (pairs s t)
  (cons-stream
   (list (stream-car s) (stream-car t))
   (interleave (stream-map (λ (x) (list (stream-car s) x))
                           (stream-cdr t))
               (interleave (stream-map (λ (x) (list x (stream-car t)))
                                       (stream-cdr s))
                           (pairs (stream-cdr s) (stream-cdr t))))))

Мои первые 20 результатовпохожи, хотя в некоторых случаях в другом порядке или с другими элементами, которые, вероятно, появятся позже в вашем решении: 

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