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 https://github.com/pgujjula/apply-merge#readme


[Skip to Readme]

Downloads

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

Candidates

Versions [RSS] 0.1.0.0, 0.1.1.0
Change log ChangeLog.md
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 <libraries@mail.preetham.io>
Revised Revision 1 made by pgujjula at 2024-05-13T12:16:15Z
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:21:53Z
Distributions NixOS:0.1.1.0, Stackage:0.1.1.0
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-0.1.1.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.