Data.List.ApplyMerge

Documentation

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

If given a binary function f that is non-decreasing in both arguments, and two (potentially infinite) ordered lists xs and ys, then applyMerge f xs ys is a sorted 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.

For example, to generate the 3-smooth numbers (Wikipedia):

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

For more examples, see README#examples.

applyMergeBy :: (c -> c -> Ordering) -> (a -> b -> c) -> [a] -> [b] -> [c]

Like applyMerge, but uses a custom comparison function.

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

Like applyMerge, but applies a custom projection function before performing comparisons.

For example, to compute the Gaussian integers, ordered by norm:

zs :: [Integer]
zs = 0 : concatMap (\i -> [i, -i]) [1..]

gaussianIntegers :: [GaussianInteger]      -- `GaussianInteger` from arithmoi
gaussianIntegers = applyMergeOn norm (:+) zs zs