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

[ bsd3, data, library ] [ Propose Tags ]

Please see the README on GitHub at

[Skip to Readme]


Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


Versions [RSS],
Change log
Dependencies base (>=4.16 && <4.21), containers (>=0.6 && <0.8), pqueue (>=1.4 && <1.6), reflection (>=2.1 && <2.2) [details]
License BSD-3-Clause
Copyright Preetham Gujjula
Author Preetham Gujjula
Maintainer Preetham Gujjula <>
Revised Revision 1 made by pgujjula at 2024-05-13T12:16:15Z
Category Data
Home page
Bug tracker
Source repo head: git clone
Uploaded by pgujjula at 2024-05-11T19:21:53Z
Distributions NixOS:, Stackage:
Downloads 40 total (22 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]

Readme for apply-merge-

[back to package description]


CI REUSE status Hackage Version

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


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/ for caveats.


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


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/ for a full exposition of the applyMerge function and its implementation.


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


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.