= Stream sharing in Hamming-number construction
The <Hamming number> stream merges its shared multiples by two, three and five. To emit its first $n$ values, each of the fixed number of mapped streams and merge nodes advances at most $n+O(1)$ positions. With <lazy evaluation> that shares each evaluated list cell, this takes $\Theta(n)$ comparisons and fixed-factor multiplications. The statement counts arithmetic operations, rather than bits: the growing exact <integers> make their bit-operation costs larger. Recomputing independent copies of the recursively defined stream loses this sharing argument.
Back to article page
