@hackage apply-merge0.1.1.0

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

  • Installation

  • Tested Compilers

  • Dependencies (4)

    • base >=4.16 && <4.17 || >=4.17 && <4.18 || >=4.18 && <4.19 || >=4.19 && <4.20 || >=4.20 && <4.21 || >=4.21 && <4.22 || >=4.22 && <4.23
    • containers >=0.6 && <0.7 || >=0.7 && <0.8 || >=0.8 && <0.9
    • pqueue >=1.4 && <1.5 || >=1.5 && <1.6 || >=1.6 && <1.7 || >=1.7 && <1.8
    • reflection >=2.1 && <2.2
      • Show all…

  • Dependents (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 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.