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

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain] [Publish]

Please see the README on GitHub at https://github.com/pgujjula/apply-merge#readme


[Skip to Readme]

Properties

Versions 0.1.0.0, 0.1.0.0, 0.1.1.0
Change log ChangeLog.md
Dependencies base (>=4.16 && <4.20), containers (>=0.6 && <0.7), pqueue (>=1.4 && <1.6), reflection (>=2.1 && <2.2) [details]
License BSD-3-Clause
Copyright Preetham Gujjula
Author Preetham Gujjula
Maintainer Preetham Gujjula <libraries@mail.preetham.io>
Category Data
Home page https://github.com/pgujjula/apply-merge#readme
Bug tracker https://github.com/pgujjula/apply-merge/issues
Source repo head: git clone https://github.com/pgujjula/apply-merge
Uploaded by pgujjula at 2024-05-11T19:12:51Z

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


Readme for apply-merge-0.1.0.0

[back to package description]

apply-merge

CI REUSE status Hackage Version

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 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..]

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.