难以理解/可视化 SICP 流汉明数程序
Trouble understanding / visualising SICP streams Hamming numbers program
我基本上停留在 SICP 的练习 3.56 上。问题是这样的：
Exercise 3.56. A famous problem, first raised by R. Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2, 3, or 5. One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2, 3, and 5. But this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement. As an alternative, let us call the required stream of numbers S and notice the following facts about it.
- S begins with 1.
- The elements of (scale-stream S 2) are also elements of S.
- The same is true for (scale-stream S 3) and (scale-stream 5 S).
- These are all the elements of S.
Now all we have to do is combine elements from these sources. For this we define a procedure merge that combines two ordered streams into one ordered result stream, eliminating repetitions:
(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)))))))))
Then the required stream may be constructed with merge, as follows:
(define S (cons-stream 1 (merge <??> <??>)))
Fill in the missing expressions in the places marked above.
在这个特定问题之前，我已经能够使用信号处理框图来可视化和理解这些隐式流定义，并将原始流反馈给过程。
但我基本上遇到了这个特殊问题，我查找了解决方案，但我发现无法想象该解决方案在我的 head/paper 中的工作方式。
对于这类问题，是否有理解和提出解决方案的技巧？
这是有效的解决方案：
(define S
(cons-stream 1 (merge (scale-stream S 2)
(merge (scale-stream S 3)
(scale-stream S 5)))))
提前致谢。
这是我最好的形象化尝试。但是我确实很挣扎，感觉就像一条三头蛇吃自己的尾巴。
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*?
________________________________________________________________
所以它可能更像是一条蛇，一个头被它的三个尾巴交替咬伤。
作为正确命名的问题，merge 不应删除重复项，因为它的名称表明它是 mergesort 的一部分，应该保留它们。 Union 是此类操作的更好名称，它通过增加唯一数字列表来表示（此处）集合，它应该通过删除只能来自 both[= 的重复项来保留该约束172=] 的参数。
回到问题本身，我们符号化的写成
S<sub>235</sub> = {1} ∪ 2*S<sub>235</sub> ∪ 3*S<sub> 235</sub>∪5*S<sub>235</sub>
Premature implementation is the mother of all evil! （等等，什么？） 我们甚至还不会尝试确定这些 ∪s 做他们的工作，甚至不是按什么顺序。甚至有多少个术语：
S<sub>23</sub> = {1} ∪ 2*S<sub>23</sub> ∪ 3*S<sub> 23</sub>
甚至
S<sub>2</sub> = {1} ∪ 2*S<sub>2</sub>
现在这看起来很简单。我们甚至可以在这里 简单地 假实现 A 和 B 的并集，首先获取 A 的所有元素，然后 - - B。在这里它会工作得很好，因为在 ∪ 的左输入中只有一个元素：
{1} ----∪-->--->--S₂--.--->S₂
/ \
\______*2_______/
---<----<---
这是如何工作的？ 1 进入 ∪ combiner，先退出，无条件（注意这个 发现的要求 很重要，因为如果 ∪ 必须立即检查它的两个参数，我们就会陷入无限循环，成为 [=227= 中的 黑洞 ] argot), 被 . 拆分器 一分为二，然后 1 的第一个副本继续到输出点，而 1 通过 *2 乘数返回，结果 2 这次在右边返回 ∪， 没有反对 上的任何东西离开（此时已经是空的），并以相同的方式继续，因此 2 到达输出点，然后 4，然后 8，等等。
换句话说，S₂包含了{1}的所有元素；加上经过 *2 乘数一次的 {1} 的所有元素；和两次；三遍；依此类推 - 2 的所有幂按递增顺序排列：
S<sub>2</sub> = {1} ∪ 2*{1} ∪ 2*2*{1} ;; == {1, 2, 4, 8, 16, 32, ...}
∪ 2*2*2*{1}
∪ 2*2*2*2*{1}
∪ ..........
图中的两个 S₂ 是相同的，因为我们在分流点从中吸取的任何东西都不会影响它。
这不是很有趣吗？
那么我们如何将 3 的倍数加到它上面呢？一种方法是
S<sub>23</sub> = S<sub>2</sub> ∪ 3*S<sub>23</sub>
{1} ----∪-->--->--S₂--.---S₂----∪-->--->--S₂₃--.--->S₂₃
/ \ / \
\______*2_______/ \______*3________/
---<----<--- ---<----<---
这里 S₂ 的 1 进入第二个 ∪ 组合器并继续到输出点 S₂₃ 以及通过 *3 乘数返回，变成 3。现在第二个 ∪ 有 2,4,8,... 和 3,... 作为输入； 2经过并变成6。接下来，∪ 有 4,8,16,... 和 3,6,...； 3 通过。接下来，4；等等，等等，等等等等。
因此 S₂ 的所有元素都是 S₂₃ 的一部分，但是 S₂ 的所有元素也是 *3 一次和两次乘数的一部分，等等，-- 2 和 3 的所有幂相乘，按递增顺序：
S<sub>23</sub> = S<sub>2</sub> ∪ 3*S<sub>2</sub> ∪ 3*3*S<sub>2</sub> ;; = S<sub>2</sub> ∪ 3*( S<sub>2</sub> ∪ 3*S<sub>2</sub>
∪ 3*3*3*S<sub>2</sub> ;; ∪ 3*3*S<sub>2</sub>
∪ 3*3*3*3*S<sub>2</sub> ;; ∪ 3*3*3*S<sub>2</sub>
∪ .......... ;; ∪ ........ ) !!
为什么递增顺序？如何？为什么，那是∪的责任！您好，另一个 发现了需求。无论从哪一侧进入它，它都必须先产生较小的元素，然后再产生较大的元素。
如果两者相等怎么办？在这个方案中，我们甚至需要关心这个问题吗？这会发生在这里吗？
不能。因此我们可以将 ∪ 这里 实现为 merge，而不是 union（但 记住第一个发现的要求! -- 它仍然有效吗？需要吗？添加新案例)。 Merge 应该比 union 更有效，因为它不关心相等的情况。
还有5的倍数？我们继续，因为
S<sub>235</sub> = S<sub>23</sub> ∪ 5*S<sub>235</sub>
{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 -->--/ /
\ /
\__________<__________<__________<_________<_______________/
去重"union"在书中叫做merge
我基本上停留在 SICP 的练习 3.56 上。问题是这样的：
Exercise 3.56. A famous problem, first raised by R. Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2, 3, or 5. One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2, 3, and 5. But this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement. As an alternative, let us call the required stream of numbers S and notice the following facts about it.
- S begins with 1.
- The elements of (scale-stream S 2) are also elements of S.
- The same is true for (scale-stream S 3) and (scale-stream 5 S).
- These are all the elements of S.
Now all we have to do is combine elements from these sources. For this we define a procedure merge that combines two ordered streams into one ordered result stream, eliminating repetitions:
(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)))))))))Then the required stream may be constructed with merge, as follows:
(define S (cons-stream 1 (merge <??> <??>)))Fill in the missing expressions in the places marked above.
在这个特定问题之前，我已经能够使用信号处理框图来可视化和理解这些隐式流定义，并将原始流反馈给过程。
但我基本上遇到了这个特殊问题，我查找了解决方案，但我发现无法想象该解决方案在我的 head/paper 中的工作方式。
对于这类问题，是否有理解和提出解决方案的技巧？
这是有效的解决方案：
(define S
(cons-stream 1 (merge (scale-stream S 2)
(merge (scale-stream S 3)
(scale-stream S 5)))))
提前致谢。
这是我最好的形象化尝试。但是我确实很挣扎，感觉就像一条三头蛇吃自己的尾巴。
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*?
________________________________________________________________
所以它可能更像是一条蛇，一个头被它的三个尾巴交替咬伤。
作为正确命名的问题，merge 不应删除重复项，因为它的名称表明它是 mergesort 的一部分，应该保留它们。 Union 是此类操作的更好名称，它通过增加唯一数字列表来表示（此处）集合，它应该通过删除只能来自 both[= 的重复项来保留该约束172=] 的参数。
回到问题本身，我们符号化的写成
S<sub>235</sub> = {1} ∪ 2*S<sub>235</sub> ∪ 3*S<sub> 235</sub>∪5*S<sub>235</sub>
Premature implementation is the mother of all evil! （等等，什么？） 我们甚至还不会尝试确定这些 ∪s 做他们的工作，甚至不是按什么顺序。甚至有多少个术语：
S<sub>23</sub> = {1} ∪ 2*S<sub>23</sub> ∪ 3*S<sub> 23</sub>
甚至
S<sub>2</sub> = {1} ∪ 2*S<sub>2</sub>
现在这看起来很简单。我们甚至可以在这里 简单地 假实现 A 和 B 的并集，首先获取 A 的所有元素，然后 - - B。在这里它会工作得很好，因为在 ∪ 的左输入中只有一个元素：
{1} ----∪-->--->--S₂--.--->S₂
/ \
\______*2_______/
---<----<---
这是如何工作的？ 1 进入 ∪ combiner，先退出，无条件（注意这个 发现的要求 很重要，因为如果 ∪ 必须立即检查它的两个参数，我们就会陷入无限循环，成为 [=227= 中的 黑洞 ] argot), 被 . 拆分器 一分为二，然后 1 的第一个副本继续到输出点，而 1 通过 *2 乘数返回，结果 2 这次在右边返回 ∪， 没有反对 上的任何东西离开（此时已经是空的），并以相同的方式继续，因此 2 到达输出点，然后 4，然后 8，等等。
换句话说，S₂包含了{1}的所有元素；加上经过 *2 乘数一次的 {1} 的所有元素；和两次；三遍；依此类推 - 2 的所有幂按递增顺序排列：
S<sub>2</sub> = {1} ∪ 2*{1} ∪ 2*2*{1} ;; == {1, 2, 4, 8, 16, 32, ...}
∪ 2*2*2*{1}
∪ 2*2*2*2*{1}
∪ ..........
图中的两个 S₂ 是相同的，因为我们在分流点从中吸取的任何东西都不会影响它。
这不是很有趣吗？
那么我们如何将 3 的倍数加到它上面呢？一种方法是
S<sub>23</sub> = S<sub>2</sub> ∪ 3*S<sub>23</sub>
{1} ----∪-->--->--S₂--.---S₂----∪-->--->--S₂₃--.--->S₂₃
/ \ / \
\______*2_______/ \______*3________/
---<----<--- ---<----<---
这里 S₂ 的 1 进入第二个 ∪ 组合器并继续到输出点 S₂₃ 以及通过 *3 乘数返回，变成 3。现在第二个 ∪ 有 2,4,8,... 和 3,... 作为输入； 2经过并变成6。接下来，∪ 有 4,8,16,... 和 3,6,...； 3 通过。接下来，4；等等，等等，等等等等。
因此 S₂ 的所有元素都是 S₂₃ 的一部分，但是 S₂ 的所有元素也是 *3 一次和两次乘数的一部分，等等，-- 2 和 3 的所有幂相乘，按递增顺序：
S<sub>23</sub> = S<sub>2</sub> ∪ 3*S<sub>2</sub> ∪ 3*3*S<sub>2</sub> ;; = S<sub>2</sub> ∪ 3*( S<sub>2</sub> ∪ 3*S<sub>2</sub>
∪ 3*3*3*S<sub>2</sub> ;; ∪ 3*3*S<sub>2</sub>
∪ 3*3*3*3*S<sub>2</sub> ;; ∪ 3*3*3*S<sub>2</sub>
∪ .......... ;; ∪ ........ ) !!
为什么递增顺序？如何？为什么，那是∪的责任！您好，另一个 发现了需求。无论从哪一侧进入它，它都必须先产生较小的元素，然后再产生较大的元素。
如果两者相等怎么办？在这个方案中，我们甚至需要关心这个问题吗？这会发生在这里吗？
不能。因此我们可以将 ∪ 这里 实现为 merge，而不是 union（但 记住第一个发现的要求! -- 它仍然有效吗？需要吗？添加新案例)。 Merge 应该比 union 更有效，因为它不关心相等的情况。
还有5的倍数？我们继续，因为
S<sub>235</sub> = S<sub>23</sub> ∪ 5*S<sub>235</sub>
{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 -->--/ /
\ /
\__________<__________<__________<_________<_______________/
去重"union"在书中叫做merge