 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/functional-programming-design-and-analysis-of-algorithms/2/c/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 2 / c / Solution by

Codex  0 2026-10-31

The first six shared values are [1,2,3,4,5,6]. At the logical merge frontier after emitting six, the streams have these consumed prefixes and next candidates:

Stream	Consumed values	Next candidate	Shared source cell
$2 \times$	$2, 4, 6$	$8$	fourth cell, value $4$
$3 \times$	$3, 6$	$9$	third cell, value $3$
$5 \times$	$5$	$10$	second cell, value $2$

Each row points into the same underlying lazy list, rather than recomputing an independent copy. The inner merge supplies the union of the last two rows, and the outer merge combines it with the first. Equal candidates at six advance both supplying streams. These next candidates describe the logical frontier: a demand such as take 6 hamming need not already have evaluated their numeric values.

Figure 1.
Shared Hamming-number stream after six outputs
. The three multiplier streams read earlier cells of one shared list. The pending values 8, 9 and 10 are logical next candidates, not a claim that take 6 forces them. **Details**.

 Read the full article

 New to topics? Read the docs here!