难以理解/可视化 SICP 流汉明数程序

我基本上陷入了 SICP 练习 3.56 的困境。问题是这样的：

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

• S begins with 1.
  • (scale-stream S 2) 的元素也是 S 的元素。
  • 对于（scale-stream S 3）和（scale-stream 5 S）也是如此。
  • 这些都是S的要素。

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

(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)))))

提前致谢。

作为正确命名的问题，merge不应该删除重复项，因为它的名字表明它是mergesort这应该保护它们。Union是此类操作的更好名称，它通过增加唯一数字列表来表示集合（此处），它应该通过删除只能来自的重复项来保留该约束both其论点。

回到问题本身，我们把它象征性地写成

S235 = {1} ∪ 2S235 ∪ 3S235 ∪ 5*S235

过早实施是万恶之母！ （等等，什么？）我们甚至还不会尝试确定这些到底是如何发生的∪他们做自己的工作，甚至不按什么顺序。或者甚至有多少个术语：

S23 = {1} ∪ 2S23 ∪ 3S23

or even

S2 = {1} ∪ 2*S2

现在这看起来很简单。我们甚至可以假实现联盟A and B here simply首先，考虑所有元素A，然后——的B。在这里它会工作得很好，因为这里只有一个元素∪的左输入：

 {1} ----∪-->--->--S₂--.--->S₂
        /               \        
        \______*2_______/        
          ---<----<---         

这是如何运作的？1进入∪ combiner，先退出，无条件地（注意这个发现的需求很重要，因为如果∪必须立即检查它的两个参数，我们就会陷入无限循环，黑洞在 Haskell 行话中），被分成两部分. splitter，然后第一个副本1继续前进到输出点，而第二个副本1回到过去*2乘数，所得结果2输入返回∪这次在右边，无人反对左边的任何东西（此时已经是空的），并以同样的方式继续，所以2到达输出点，然后4, then 8等等等等。

换句话说，S₂包含所有元素{1};加上所有元素{1}那个经历了*2乘数一次；和两次；以及三次；等等——所有的权力2按递增顺序：

S2 = {1} ∪ 2*{1} ∪ 2*2*{1}                ;; == {1, 2, 4, 8, 16, 32, ...}
                 ∪ 2*2*2*{1}
                 ∪ 2*2*2*2*{1}
                 ∪ ..........

The two S₂图中的 是相同的，因为我们在分流点从它吸取的任何东西都不会影响它。

这不是很有趣吗？

那么我们如何去添加的倍数3到它？一种方法是

S23 = S2 ∪ 3*S23

 {1} ----∪-->--->--S₂--.---S₂----∪-->--->--S₂₃--.--->S₂₃
        /               \       /                \        
        \______*2_______/       \______*3________/        
          ---<----<---            ---<----<---         

^{Here 1 from S₂ enters the second ∪ combiner and proceeds to the output point S₂₃ as well as back through the *3 multiplier, turning into 3. Now the second ∪ has 2,4,8,... and 3,... as its inputs; 2 goes through as well as turning into 6. Next, ∪ has 4,8,16,... and 3,6,...; 3 goes through. Next, 4; etc., etc., and so on and so forth.}

因此所有元素S₂是一部分S₂₃，但所有元素也是如此S₂那个经历了*3乘数一次、两次等等——所有的幂2 and 3按递增顺序相乘：

S23 = S2 ∪ 3*S2 ∪ 3*3*S2                   ;; = S2 ∪ 3*( S2 ∪ 3*S2 
                ∪ 3*3*3*S2                 ;;               ∪ 3*3*S2 
                ∪ 3*3*3*3*S2               ;;               ∪ 3*3*3*S2 
                ∪ ..........               ;;               ∪ ........ )   !!

为什么顺序递增？如何？为什么，这就是责任∪！你好，another 发现的需求。无论从任一侧进入它，它都必须先产生较小的元素，然后再产生较大的元素。

如果两者相等该怎么办？在这个方案中，我们是否需要关心这个问题？这会发生吗？

不可以。所以我们可以实施∪ here as a merge，不作为union (but 记住第一个发现的需求！ ——现在还有效吗？需要吗？随着新病例的增加). Merge应该比union因为它不关心平等的情况。

对于的倍数5还？我们继续，作为

S235 = S23 ∪ 5*S235

 {1} ----∪-->--->--S₂--.---S₂----∪-->--->--S₂₃--.---S₂₃----∪-->--->--S₂₃₅--.--->S₂₃₅
        /               \       /                \         /                 \ 
        \______*2_______/       \______*3________/         \_______*5________/ 
          ---<----<---            ---<----<---                ---<----<---     

• 这是否描述了书中的代码？ _______
• 这是否描述了一个比书中的代码快大约两倍的代码？ _______
• 为什么它比书中的代码快两倍左右？ _______
• 这个回答有吗your问题？ _______
• 这有帮助吗you回答你的问题吗？ _______

（填空）。

也可以看看：

• 无限生成汉明序列的最新技术

本书代码的信号处理框图是：

                                  1 --->---\
                                             cons-stream ->-- S ---.---> S
    /----->---->--- *2 --->---\            /                       |
   /                            union ->--/                        /
  .-->-- *3 -->--\            /                                   /
  |                union ->--/                                   /
  .-->-- *5 -->--/                                              /
  \                                                            /
   \__________<__________<__________<_________<_______________/

其中删除重复项的“联合”被称为merge在书里。