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.