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, andxs
andys
are (potentially infinite) ordered lists, thenapplyMerge f xs ys
is an ordered list of allf x y
, for eachx
inxs
andy
inys
.Producing n elements of
applyMerge f xs ys
takes O(n log n) time and O(√n) auxiliary space, assuming thatf
andcompare
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 applyingf
to eachx
andy
, and merging the results into one sorted output. I’m still thinking of the ideal name for this function. Other options includesortedLiftA2
/orderedLiftA2
, from the idea that this function is equivalent tosort (liftA2 f xs ys)
whenxs
andys
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.