I wrote this library to introduce the function

```
applyMerge :: Ord c => (a -> b -> c) -> [a] -> [b] -> [c]
```

I haven’t seen the idea behind this function before. Some documentation from the README:

If

`f`

is a binary function that is non-decreasing in both arguments, and`xs`

and`ys`

are (potentially infinite) ordered lists, then`applyMerge f xs ys`

is an ordered list of all`f x y`

, for each`x`

in`xs`

and`y`

in`ys`

.Producing n elements of

`applyMerge f xs ys`

takes O(n log n) time and O(√n) auxiliary space, assuming that`f`

and`compare`

take O(1) time.## Examples

With

`applyMerge`

, we can implement a variety of complex algorithms succinctly. For example, the Sieve of Erastosthenes to generate prime numbers:`primes :: [Int] primes = 2 : ([3..] `minus` composites) -- `minus` from data-ordlist composites :: [Int] composites = applyMerge (*) primes [2..]`

3-smooth numbers (Wikipedia):

`smooth3 :: [Integer] smooth3 = applyMerge (*) (iterate (*2) 1) (iterate (*3) 1)`

Gaussian integers, ordered by norm (Wikipedia):

`zs :: [Integer] zs = 0 : concatMap (\i -> [i, -i]) [1..] gaussianIntegers :: [GaussianInteger] -- `GaussianInteger` from arithmoi gaussianIntegers = map snd (applyMerge (\x y -> (norm (x :+ y), x :+ y)) zs zs)`

Square-free integers (Wikipedia):

`squarefrees :: [Int] squarefrees = [1..] `minus` applyMerge (*) (map (^2) primes) [1..]`

## Naming

The name

`applyMerge`

comes from the idea of applying`f`

to each`x`

and`y`

, and merging the results into one sorted output. I’m still thinking of the ideal name for this function. Other options include`sortedLiftA2`

/`orderedLiftA2`

, from the idea that this function is equivalent to`sort (liftA2 f xs ys)`

when`xs`

and`ys`

are finite. If you have any ideas on the naming, let me know!

See ALGORITHM.md for a full exposition of the `applyMerge`

function and its implementation.

I’m open to questions/comments/feedback of any kind, especially about whether you’ve seen this idea before, and on the name of the function.