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

Compare the two heads, emitting one copy of a tie and advancing both inputs in that case:

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge xs@(x:xt) ys@(y:yt)
  | x < y     = x : merge xt ys
  | x > y     = y : merge xs yt
  | otherwise = x : merge xt yt

The emitted head is the smallest remaining value, so induction preserves strict order and removes duplicates. The extra empty-input cases also make the definition useful on finite lists.

There is a mathematical qualification to the unrestricted infinite-input claim: the union must be enumerable in this order. If one input increases to one from below and the other starts at two, no finite output position can contain two. Locally finite sorted-stream merge excludes this obstruction, and applies to the positive integer streams needed below.

b

 0  0

Solution

 0  0

Tie the three scaled streams back to the same shared lazy list:

hamming :: [Integer]
hamming = 1 : merge (map (2*) hamming)
                    (merge (map (3*) hamming) (map (5*) hamming))

The resulting values are precisely the Hamming numbers

2^{i} 3^{j} 5^{k}

for nonnegative integers

i, j, k

. Every noninitial value has a smaller predecessor obtained by removing a factor, so the recursive demand can be supplied from earlier cells. This is the productivity argument for a sorted multiplicative closure stream. The merge algorithm removes duplicate representations such as

2 \cdot 3 = 3 \cdot 2

, retaining strict order and every generated value.

c

 0  0

Solution

 0  0

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**.

d

 0  0

Solution

 0  0

The cost is $Θ (n)$ arithmetic and comparison operations under shared lazy evaluation and unit-cost operations on the numeric values. There are only three mapped streams and two merge nodes. Before the first

n

output cells are produced, each node advances at most

n + O (1)

input positions; each advance does a bounded number of operations. Producing the

n

output cells also gives an

Ω (n)

lower bound.

This is stream sharing in Hamming-number construction. It relies on sharing the recursive list cells, and is not a bound on bit operations: multiplying or comparing arbitrarily large Integer values costs more as their representations grow.

e

 0  0

Solution

 0  0

For exact ordered numbers, first discard multipliers equal to one and reject those below one:

hamming' :: (Ord a, Num a) => [a] -> [a]
hamming' as
  | any (<1) as = error "multipliers below one violate the ordered contract"
  | otherwise  = hs
  where
    bs = filter (>1) as
    hs = 1 : case bs of
               [] -> []
               _  -> foldr1 merge [map (a*) hs | a <- bs]

The type signature has exactly the numeric and ordering constraints used by the definition. For a finite nonempty collection of multipliers greater than one, this is the same sorted multiplicative closure stream construction as before, merging one scaled copy per multiplier. It is infinite and strictly increasing; local finiteness below any bound and the smaller-predecessor argument prove completeness and productivity. In particular, [2,3,5] reproduces hamming.

The literal contract for arbitrary positive multipliers is impossible. A multiplier strictly between zero and one would require a value smaller than the initial one; an empty list or the list [1] generates only one value. The definition returns the finite closure [1] in those degenerate cases. A multiplier equal to one adds no mathematical values and would introduce an unnecessary circular merge demand if left in the feedback streams. The order and growth proof assumes exact arithmetic with the usual laws; the broad numeric type alone cannot prevent floating-point rounding or bounded overflow.

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

a

Solution

b

Solution

c

Solution

d

Solution

e

Solution

 Ancestors (10)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

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

 Discussion (0)  Subscribe (1) New discussion

 Discussion (0) New discussion