apply-merge

Lift a binary, non-decreasing function onto ordered lists and order the output

Overview

This library provides a function

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

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(\sqrt{n})$ auxiliary space, assuming that f and compare take $O(1)$ time. See docs/ALGORITHM.md#note-about-memory-usage for caveats.

Examples

With applyMerge, we can implement a variety of complex algorithms succinctly. For example, the Sieve of Erastosthenes[^1] 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!

Further reading

See docs/ALGORITHM.md for a full exposition of the applyMerge function and its implementation.

Licensing

This project licensed under BSD-3-Clause (except for .gitignore, which is under CC0-1.0), and follows REUSE licensing principles.

[^1]: Note that this is really the Sieve of Erastosthenes, as defined in the classic The Genuine Sieve of Eratosthenes. Constrast this to other simple prime generation implementations, such as primes = sieve [2..] where sieve (p : xs) = p : sieve [x | x <- xs, x `rem` p > 0] which is actually trial division and not a faithful implementation of the Sieve of Erastosthenes.