= Solution
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.
Back to article page
