BSD-3-Clause licensed by Preetham Gujjula
Maintained by Preetham Gujjula
This version can be pinned in stack with:apply-merge-0.1.1.0@sha256:e617d5392133fc62f7ebbc95d27fc1167977934390e8593f20516c80b854b1cc,3857

Module documentation for 0.1.1.0

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 Erastosthenes[^1] 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.

Changes

Changelog for apply-merge

0.1.0.1

Added

  • Implementation of applyMergeOn (#1) and applyMergeBy (#3).
  • Implementation of applyMerge for NonEmpty (#2).
  • Comprehensive benchmark suite for applyMerge (#8).

Changed

  • Switched from falsify to QuickCheck in the test suite, allowing the project to be used in Stackage (link).
  • CI configured to test GHC 9.2.8, 9.4.8, 9.6.5, 9.8.2.

0.1.0.0

Added

  • Implementation of applyMerge.
  • A tasty-based test suite for applyMerge.
  • A tasty-bench benchmark suite for applyMerge.
  • Haddock documentation for applyMerge.
  • Support for GHC 9.2, 9.4, 9.6, 9.8.
  • CI testing for GHC 9.2.8, 9.4.8, 9.6.4.
  • Documentation of the library in README.md and docs/ALGORITHM.md, with feedback from meeeow on Haskell Discourse (link).