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

Question

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


练习3.56。由R. Hamming提出的一个著名问题是，以升序（无重复）枚举除2、3或5以外没有素数的所有正整数。一种显而易见的方法是简单地测试每个整数依次查看是否有2、3和5以外的任何其他因素。但这效率很低，因为随着整数变大，越来越少的整数符合要求。作为替代，让我们调用所需的数字流S并注意以下事实。


S以1开头。


（比例流S 2）的元素也是S的元素。
（比例流S 3）和（比例流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)))))))))

然后可以通过合并构造所需的流，如下所示：

(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

作为适当的命名，merge不应删除重复项，因为其名称表明它是mergesort的一部分，应保留这些重复项。 Union是此类操作的更好称呼，它可以看到（在此）通过增加唯一编号列表表示的集合，该限制应通过删除只能来自其两个自变量的重复项来保留。

回到问题本身，让我们将其象征性地写为

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

Premature implementation is the mother of all evil!（等等，什么？）我们甚至都不会尝试确定这些∪的工作方式，甚至是按照什么顺序。甚至还有多少个术语：

S23 = {1} ∪ 2*S23 ∪ 3*S23

甚至

S2 = {1} ∪ 2*S2

现在看起来很简单。我们甚至可以在这里伪造实现A和B的联合，方法很简单，首先，获取A的所有元素，然后获取B的-。在这里，它可以正常工作，因为在∪的左侧输入中只有一个元素：

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

这是如何运作的？ 1进入∪组合器，先无条件退出（注意，此发现的要求很重要，因为如果∪必须立即检查其两个参数，我们将陷入无限循环，这是一个黑洞） Haskell argot），由.拆分器分为两部分，然后1的第一个副本继续前进到输出点，而1的第二个副本通过*2乘数返回，得到的这次在右边输入2，在左边没有任何东西的反对（这时已经是空的），并以相同的方式继续，所以∪转到输出点，然后是2 ，然后是4等。

换句话说，8包含S₂的所有元素。加上一次通过{1}乘数的所有{1}元素；和两次；三遍依此类推-2的所有幂以升序排列：

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

图中的两个*2是相同的，因为无论我们在分离器点虹吸它如何，都不会对其产生影响。

这不是很有趣吗？

那么，如何添加S₂的倍数呢？一种方法是

3

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

在这里，来自S23 = S2 ∪ 3*S23的1进入第二个S₂组合器，并前进到输出点∪，然后通过S₂₃乘数返回，变成*3。现在，第二个3具有∪和2,4,8,...作为输入； 3,...会同时变为2。接下来，6具有∪和4,8,16,...； 3,6,...通过。接下来，3;等等，依此类推等等。

因此，4的所有元素都是S₂的一部分，而通过S₂₃乘数的S₂的所有元素也是一次，两次，依此类推-2和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 
                ∪ ..........               ;;               ∪ ........ )   !!

为什么要增加顺序？怎么样？为什么，这是*3的责任！您好，另一个发现的要求。无论从哪一侧进入，它都必须先产生较小的元素，然后再产生较大的元素。

如果两者相等，该怎么办？我们在此方案中是否甚至需要考虑这个问题？这有可能发生吗？

不行因此，我们可以在此处将∪实现为∪而不是merge（但请记住第一个发现的要求！-它仍然有效吗？是否需要？添加新的案例）。 union应该比Merge更有效率，因为它与等号无关。

而且也是5的倍数吗？我们继续

union

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

这是否描述了本书中的代码？ _______
这是否描述了比本书中的代码快两倍的代码？ _______
为什么它比本书中的代码快大约两倍？ _______
这回答了你的问题了吗？ _______
这是否可以帮助您回答问题？ _______


（填空）。

也可以看看：


New state of the art in unlimited generation of Hamming sequence




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

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

删除重复项的“工会”在书中称为S235 = S23 ∪ 5*S235。