Haskell - Prime Powers Excercise - Infinite merges

Question

At university my task is the following :

define the following function:

primepowers :: Integer -> [Integer]

that calculates the infinite list of the first n powers of the prime numbers for a given parameter n, sorted asc. That is, primepowers n contains in ascending order the elements of

{p^i | p is prime, 1≤i≤n}.

After working on this task I came to a dead end. I have the following four functions:

merge :: Ord t => [t] -> [t] -> [t]
merge [] b = b
merge a [] = a
merge (a:ax) (b:bx)
  | a <= b    = a : merge ax (b:bx)
  | otherwise = b : merge (a:ax) bx

primes :: [Integer] 
primes = sieve [2..]
    where sieve [] = []
          sieve (p:xs) = p : sieve (filter (not . multipleOf p) xs)
            where multipleOf p x = x `mod` p == 0   

powers :: Integer -> Integer -> [Integer] 
powers n num = map (\a -> num ^ a) [1..n]

primepowers :: Integer -> [Integer]
primepowers n = foldr merge [] (map (powers n) primes)

I think that they work independently, as I have tested with some sample inputs. merge merges two ordered lists to one ordered list primes returns infinite list of prime numbers powers calculates n powers of num (that is num^1 , num^2 ... num^n)

I try to merge everything in primepowers, but functions are not evaluated nothing happens respectively theres some kind of infinite loop.

I am not interested in optimization of primes or powers. Just I don't understand why that does not work. Or is my approach not good, not functional, not haskell?

Answer 1

I suspect the problem is: primes is an infinite list. Therefore, map (powers n) primes is an infinite list of (finite) lists. When you try to foldr merge [] them all together, merge must evaluate the head of each list...

Since there are an infinite number of lists, this is an infinite loop.

---

I would suggest transposing the structure, something like:

primepowers n = foldr merge [] [map (^i) primes | i <- [1..n]]

Answer 2

While you can probably not use this for your assignment, this can be solved quite elegantly using the primes and data-ordlist packages from Hackage.

import Data.List.Ordered
import Data.Numbers.Primes

primePowers n = mergeAll [[p^k | k <- [1..n]] | p <- primes]

Note that mergeAll is able to merge an infinite number of lists because it assumes that the heads of the lists are ordered in addition to the lists themselves being ordered. Thus, we can easily make this work for infinite powers as well:

allPrimePowers = mergeAll [[p^k | k <- [1..]] | p <- primes]

Answer 3

The reason why your program runs into an infinite loop is that you are trying to merge infinitely many lists only by using the invariant that each list is sorted in the ascending order. Before the program can output “2,” it has to know that none of the lists contains anything smaller than 2. This is impossible because there are infinitely many lists.

Answer 4

You need the following function:

mergePrio (h : l) r = h : merge l r