Merging an unbound number of ordered infinite sequences

Question

I want to generate all natural numbers together with their decomposition in prime factors, up to a certain threshold.

I came up with the following function:

vGenerate :: [a]                 -- generator set for monoid B* (Kleene star of B)
          -> (a, (a -> a -> a)) -- (identity element, generating function)
          -> (a -> Bool)        -- filter
          -> [a]                -- B* filtered
vGenerate [] (g0,_) _ = [g0]
vGenerate (e:es) (g0,g) c = 
    let coEs = vGenerate es (g0,g) c
        coE  = takeWhile (c) $ iterate (g e) g0
    in concatMap (\m -> takeWhile (c) $ map (g m) coE) coEs

gen then generates all natural numbers together with their prime factors:

gen threshold =
     let b = map (\x -> (x,[x])) $ takeWhile (<= threshold) primes
         condition = (<= threshold) . fst
         g0 = (1,[])
         g = \(n,nl)(m,ml) -> ((n*m), nl ++ ml)
     in vGenerate b (g0,g) condition

primes = [2,3,5,7,11,.. ] -- pseudo code

I have the following questions:

• It is not always known in advance how many numbers we will need. Can we modify vGenerate such that it starts with a lazy infinite list of primes, and generates all the factorizations in increasing order? The challenge is that we have an infinite list of primes, for each prime an infinite list of powers of that prime number, and then have to take all possible combinations. The lists are naturally ordered by increasing first element, so they could be generated lazily.

• I documented vGenerate in terms of monoid, with the intention to keep it as abstract as possible, but perhaps this just obfuscates the code? I want to generalize it later (more as an exercise than for real usage), e.g. for generating raster points within certain constraints, which can also be put in the monoid context, so I thought it was a good start to get rid of all references to the problem space (in casu: primes). But I feel that the filtering function does not fit well in the abstraction: the generation must happen in an order that is monotonous for the metric tested by c, because recursion is terminated as soon as c is not satisfied. Any advice?

Answer 1

Have a look at mergeAll :: Ord a => [[a]] -> [a] from the data-ordlist package. It merges an unbound number of infinite sequences as long as the sequences are ordered, and the heads of the sequences are ordered. I've used it for similar problems before, for example to generate all numbers of the form 2^i*3^j.

> let numbers = mergeAll [[2^i*3^j | j <- [0..]] | i <- [0..]]
> take 20 numbers
[1,2,3,4,6,8,9,12,16,18,24,27,32,36,48,54,64,72,81,96]

You should be able to extend this to generate all numbers with their factorizations.