**Warning:** if you are currently crossing a road, be sure to reach the side *before* reading further!

# Challenge

- Given two iterables / iterators / generators (henceforth:
*producers*) - that produce elements in strictly increasing order
- (i.e. every next element is greater than the previous one, and there are no duplicates),
- construct a generator that produces all elements of the given producers
- in strictly increasing order and without duplicates.

You may *not* assume the given producers are finite.

Stub:

```
# In Python, but by all means feel free to
# solve this problem using another language.
def merge(xs, ys):
"""Merge two sorted-without-duplicates iterables
into a single sorted-without-duplicates generator.
"""
...
```

## Python test suite

```
def i(start, stop):
"""inclusive range"""
return range(start, stop + 1)
def squares():
n = 0
while True:
yield n * n
n += 1
def triangles():
n = 0
while True:
yield n * (n + 1) // 2
n += 1
FINITE_TEST_DATA = (
# overlap of 3
("1ā5 3ā7", i(1, 5), i(3, 7), (1, 2, 3, 4, 5, 6, 7)),
("3ā7 1ā5", i(3, 7), i(1, 5), (1, 2, 3, 4, 5, 6, 7)),
# overlap of 2
("1ā4 3ā7", i(1, 4), i(3, 7), (1, 2, 3, 4, 5, 6, 7)),
("3ā7 1ā4", i(3, 7), i(1, 4), (1, 2, 3, 4, 5, 6, 7)),
# overlap of 1
("1ā4 4ā7", i(1, 4), i(4, 7), (1, 2, 3, 4, 5, 6, 7)),
("4ā7 1ā4", i(4, 7), i(1, 4), (1, 2, 3, 4, 5, 6, 7)),
# seamless
("1ā3 4ā6", i(1, 3), i(4, 6), (1, 2, 3, 4, 5, 6)),
("4ā6 1ā3", i(4, 6), i(1, 3), (1, 2, 3, 4, 5, 6)),
# gap of 1
("1ā3 5ā7", i(1, 3), i(5, 7), (1, 2, 3, 5, 6, 7)),
("5ā7 1ā3", i(5, 7), i(1, 3), (1, 2, 3, 5, 6, 7)),
# gap of 2
("1ā3 6ā8", i(1, 3), i(6, 8), (1, 2, 3, 6, 7, 8)),
("6ā8 1ā3", i(6, 8), i(1, 3), (1, 2, 3, 6, 7, 8)),
# alternating
("0,2ā8 1,3ā7", range(0, 8, 2), range(1, 8, 2), (0, 1, 2, 3, 4, 5, 6, 7)),
("1,3ā7 0,2ā8", range(1, 8, 2), range(0, 8, 2), (0, 1, 2, 3, 4, 5, 6, 7)),
# emptiness
("ā 1ā3", range(0), i(1, 3), (1, 2, 3)),
("1ā3 ā", i(1, 3), range(0), (1, 2, 3)),
("ā ā", range(0), range(0), ()),
# misc.
("0ā9 0,2ā8", range(0, 10), range(0, 10, 2), (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)),
("0,2ā8 0ā9", range(0, 10, 2), range(0, 10), (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)),
)
for name, left, right, desired in FINITE_TEST_DATA:
actual = (*merge(left, right),)
if actual != desired:
print(f"{name = }\n {desired = }\n {actual = }")
# can handle infinite input as well
m = merge(squares(), triangles())
s = [next(m) for _ in range(20)]
if s != [0, 1, 3, 4, 6, 9, 10, 15, 16, 21, 25, 28, 36, 45, 49, 55, 64, 66, 78, 81]:
print(
"If you can read this something weird is going on,\n"
" as either a crash or success is expected."
)
```

## Haskell test suite

```
module Main where
-- To run the tests:
-- $ runghc Main.hs
import Control.Monad
merge :: Ord a => [a] -> [a] -> [a]
merge = error "you need to implement this function"
main :: IO ()
main = do
forM_ finiteTests $ \(name, xs, ys, desired) -> do
let actual = merge xs ys
when (actual /= desired) $ do
putStrLn $ "name = " ++ name
putStrLn $ " desired = " ++ show desired
putStrLn $ " actual = " ++ show actual
let m = merge squares triangles
when (take 20 m /= [0, 1, 3, 4, 6, 9, 10, 15, 16, 21, 25, 28, 36, 45, 49, 55, 64, 66, 78, 81]) $ do
putStrLn "If you can read this something weird is going on,"
putStrLn " as either a crash or success is expected."
finiteTests :: [(String, [Integer], [Integer], [Integer])]
finiteTests =
[ -- overlap of 3
("1ā5 3ā7", [1 .. 5], [3 .. 7], [1, 2, 3, 4, 5, 6, 7]),
("3ā7 1ā5", [3 .. 7], [1 .. 5], [1, 2, 3, 4, 5, 6, 7]),
-- overlap of 2
("1ā4 3ā7", [1 .. 4], [3 .. 7], [1, 2, 3, 4, 5, 6, 7]),
("3ā7 1ā4", [3 .. 7], [1 .. 4], [1, 2, 3, 4, 5, 6, 7]),
-- overlap of 1
("1ā4 4ā7", [1 .. 4], [4 .. 7], [1, 2, 3, 4, 5, 6, 7]),
("4ā7 1ā4", [4 .. 7], [1 .. 4], [1, 2, 3, 4, 5, 6, 7]),
-- seamless
("1ā3 4ā6", [1 .. 3], [4 .. 6], [1, 2, 3, 4, 5, 6]),
("4ā6 1ā3", [4 .. 6], [1 .. 3], [1, 2, 3, 4, 5, 6]),
-- gap of 1
("1ā3 5ā7", [1 .. 3], [5 .. 7], [1, 2, 3, 5, 6, 7]),
("5ā7 1ā3", [5 .. 7], [1 .. 3], [1, 2, 3, 5, 6, 7]),
-- gap of 2
("1ā3 6ā8", [1 .. 3], [6 .. 8], [1, 2, 3, 6, 7, 8]),
("6ā8 1ā3", [6 .. 8], [1 .. 3], [1, 2, 3, 6, 7, 8]),
-- alternating
("0,2ā8 1,3ā7", [0, 2 .. 7], [1, 3 .. 7], [0, 1, 2, 3, 4, 5, 6, 7]),
("1,3ā7 0,2ā8", [1, 3 .. 7], [0, 2 .. 7], [0, 1, 2, 3, 4, 5, 6, 7]),
-- emptiness
("ā 1ā3", [], [1 .. 3], [1, 2, 3]),
("1ā3 ā", [1 .. 3], [], [1, 2, 3]),
("ā ā", [], [], []),
-- misc.
("0ā9 0,2ā8", [0 .. 9], [0, 2 .. 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]),
("0,2ā8 0ā9", [0, 2 .. 9], [0 .. 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
]
squares, triangles :: [Integer]
squares = map (^ 2) [0 ..]
triangles = map (\n -> n * (n + 1) `div` 2) [0 ..]
```

## Whence this problem?

Iām working on Approaches for *Sum of Multiples*. This subproblem turned up. I already solved it myself, but am curious to see what other approaches exist.