stream - 无法理解/可视化 SICP 流 Hamming 数字程序

Question

我基本上被困在 SICP 的练习 3.56 上。问题是这样的：

练习 3.56。一个著名的问题，首先由 R. Hamming 提出，以不重复的升序枚举所有除 2、3 或 5 之外没有素因数的正整数。一个明显的方法是简单地测试每个整数反过来看它是否具有除 2、3 和 5 之外的任何因子。但这非常低效，因为随着整数变大，符合要求的整数越来越少。作为替代方案，让我们调用所需的数字流 S 并注意以下有关它的事实。

• S 以 1 开头。
  • (scale-stream S 2) 的元素也是 S 的元素。
  • (scale-stream S 3) 和 (scale-stream 5 S) 也是如此。
  • 这些都是S的元素。

现在我们要做的就是结合这些来源的元素。为此，我们定义了一个过程合并，将两个有序流合并为一个有序结果流，消除重复：

(define (merge s1 s2)
   (cond ((stream-null? s1) s2)
         ((stream-null? s2) s1)
         (else
          (let ((s1car (stream-car s1))
                (s2car (stream-car s2)))
            (cond ((< s1car s2car)
                   (cons-stream s1car (merge (stream-cdr s1) s2)))
                  ((> s1car s2car)
                   (cons-stream s2car (merge s1 (stream-cdr s2))))
                  (else
                   (cons-stream s1car
                                (merge (stream-cdr s1)
                                       (stream-cdr s2)))))))))

然后可以用merge构造所需的流，如下：

(define S (cons-stream 1 (merge <??> <??>)))

在上面标记的地方填写缺少的表达式。

在这个特定问题之前，我已经能够使用信号处理框图来可视化和理解这些隐式流定义，并将原始流反馈给过程。

但是我基本上已经遇到了这个特殊问题，我已经查找了解决方案，但我发现无法想象解决方案在我的头脑/论文中是如何工作的。

有没有什么技巧可以帮助我们理解这些问题并提出解决方案？

这是有效的解决方案：

(define S 
  (cons-stream 1 (merge (scale-stream S 2)
                        (merge (scale-stream S 3)
                               (scale-stream S 5)))))

提前致谢。

Answer 1

这是我将其可视化的最佳尝试。但我确实很挣扎，感觉就像一条三头蛇在吃自己的尾巴。

If we say the values of the stream S are s0, s1, s2, ..., then 
initially we only know the first value, s0.

               s0   s1   s2   s3   s4   s5   s6   s7   s8   s9   s10
           S = 1    ?    ?    ?    ?    ?    ?    ?    ?    ?    ?  

But we do know the three scale-streams will be producing multiples of
these values, on demand:

               s0   s1   s2   s3   s4   s5   s6   s7   s8   s9   s10
           S = 1    ?    ?    ?    ?    ?    ?    ?    ?    ?    ?  

    scale-2:   2*1  2*?  2*?  2*?  2*?  2*?  2*?  2*?  2*?  2*?  2*?
    scale-3:   3*1  3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?
    scale-5:   5*1  5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?
    ________________________________________________________________


Merge will initially select the lowest of the numbers at the heads of
these three streams, forcing their calculation in the process:

               s0   s1   s2   s3   s4   s5   s6   s7   s8   s9   s10
           S = 1    ?    ?    ?    ?    ?    ?    ?    ?    ?    ?  

    scale-2:  [2]  2*?  2*?  2*?  2*?  2*?  2*?  2*?  2*?  2*?  2*?
    scale-3:   3   3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?
    scale-5:   5   5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?
    ________________________________________________________________


 So s1 will now have the value 2:

               s0   s1   s2   s3   s4   s5   s6   s7   s8   s9   s10
           S = 1   [2]   ?    ?    ?    ?    ?    ?    ?    ?    ?  

    scale-2:        2*2  2*?  2*?  2*?  2*?  2*?  2*?  2*?  2*?  2*?
    scale-3:   3    3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?
    scale-5:   5    5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?
    ________________________________________________________________


Merge will now select 3 as the minimum of 4, 3, and 5:

               s0   s1   s2   s3   s4   s5   s6   s7   s8   s9   s10
           S = 1    2    ?    ?    ?    ?    ?    ?    ?    ?    ?  

    scale-2:        4    2*?  2*?  2*?  2*?  2*?  2*?  2*?  2*?  2*?
    scale-3:  [3]   3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?
    scale-5:   5    5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?
    ________________________________________________________________


and will put it into the next slot in the result stream S, s2:

               s0   s1   s2   s3   s4   s5   s6   s7   s8   s9   s10
           S = 1    2   [3]   ?    ?    ?    ?    ?    ?    ?    ?  

    scale-2:        4    2*?  2*?  2*?  2*?  2*?  2*?  2*?  2*?  2*?
    scale-3:        3*2  3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?
    scale-5:   5    5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?
    ________________________________________________________________


Scale-2's head is selected again:

               s0   s1   s2   s3   s4   s5   s6   s7   s8   s9   s10
           S = 1    2    3   [4]   ?    ?    ?    ?    ?    ?    ?  

    scale-2:             2*3  2*?  2*?  2*?  2*?  2*?  2*?  2*?  2*?
    scale-3:        6    3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?
    scale-5:   5    5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?
    ________________________________________________________________


And then 5 is selected from scale-5 and placed in the result:

               s0   s1   s2   s3   s4   s5   s6   s7   s8   s9   s10
           S = 1    2    3    4   [5]   ?    ?    ?    ?    ?    ?  

    scale-2:             6    2*?  2*?  2*?  2*?  2*?  2*?  2*?  2*?
    scale-3:        6    3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?
    scale-5:        5*2  5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?
    ________________________________________________________________


Two streams have 6 at their head, both are consumed but only one 6 
is placed in the result:

               s0   s1   s2   s3   s4   s5   s6   s7   s8   s9   s10
           S = 1    2    3    4    5   [6]   ?    ?    ?    ?    ?  

    scale-2:                  2*4  2*?  2*?  2*?  2*?  2*?  2*?  2*?
    scale-3:             3*3  3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?
    scale-5:        10   5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?
    ________________________________________________________________


And a few more iterations:

               s0   s1   s2   s3   s4   s5   s6   s7   s8   s9   s10
           S = 1    2    3    4    5    6   [8]   ?    ?    ?    ?  

    scale-2:                       2*5  2*?  2*?  2*?  2*?  2*?  2*?
    scale-3:             9    3*?  3*?  3*?  3*?  3*?  3*?  3*?  3*?
    scale-5:        10   5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?
    ________________________________________________________________


               s0   s1   s2   s3   s4   s5   s6   s7   s8   s9   s10
           S = 1    2    3    4    5    6    8   [9]   ?    ?    ?  

    scale-2:                       10   2*?  2*?  2*?  2*?  2*?  2*?
    scale-3:                  3*4  3*?  3*?  3*?  3*?  3*?  3*?  3*?
    scale-5:        10   5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?
    _________________________________________________________________


               s0   s1   s2   s3   s4   s5   s6   s7   s8   s9   s10
           S = 1    2    3    4    5    6    8    9   [10]  ?    ?  

    scale-2:                            2*6  2*?  2*?  2*?  2*?  2*?
    scale-3:                  12   3*?  3*?  3*?  3*?  3*?  3*?  3*?
    scale-5:             5*3  5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?
    ________________________________________________________________


               s0   s1   s2   s3   s4   s5   s6   s7   s8   s9   s10
           S = 1    2    3    4    5    6    8    9    10  [12]  ?  

    scale-2:                                 2*8  2*?  2*?  2*?  2*?
    scale-3:                       3*5  3*?  3*?  3*?  3*?  3*?  3*?
    scale-5:             15   5*?  5*?  5*?  5*?  5*?  5*?  5*?  5*?
    _________________________________________________________________


               s0   s1   s2   s3   s4   s5   s6   s7   s8   s9   s10
           S = 1    2    3    4    5    6    8    9    10   12  [15]

    scale-2:                                 16   2*?  2*?  2*?  2*?
    scale-3:                            3*6  3*?  3*?  3*?  3*?  3*?
    scale-5:                  5*4  5*?  5*?  5*?  5*?  5*?  5*?  5*?
    ________________________________________________________________

所以也许它更像一条蛇，一个头从它的三个尾巴上交替咬一口。

Answer 2