7

Let's say I want to get a sorted infinite list of all primepowers up to exponent n.

I have got a function to merge two sorted lists and a function that gives me primes.

merge :: Ord t => [t] -> [t] -> [t]
merge (x:xs) (y:ys)
    | (x <= y) = x : merge xs (y:ys)
    | otherwise = y : merge (x:xs) ys
merge xs [] = xs
merge [] ys = ys

primes :: [Integer]
primes = sieve [2..]
    where
        sieve [] = []
        sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs)

I have two versions of the listOfPrimepowers function:

primepowers :: Integer -> [Integer]
primepowers n = foldr (merge) [] (listOfPrimepowers n)    

-- terminating
listOfPrimepowers' n = map(\x -> (map(\y -> y ^ x) primes)) [1..n]

-- non terminating    
listOfPrimepowers'' n = map(\x -> (map(\y -> x ^ y) [1..n])) primes

One delivers the correct result and the other one doesn't. The only difference is, that the first version maps the primepowers in a way like [[2,3,5,7, ...],[4,9,25,...]] and the second version maps the primepowers like [[2,4,8],[3,9,27],[5,25,125], ...]. You see, the infinity is at another level in the list.

Do you have an explanation why the 2nd function doesn't produce any output?

2

4 Answers 4

8

It is caused by foldr merge having to look through all the lists to find the minimal element at the head of one of the lists. If foldr merge is given a infinite list of finite lists, foldr merge cannot ever compute the first element of the list - it keeps looking for the minimal element of the rest of the list of lists, before it can compare it to the first element of the first list - 2. On the other hand, if foldr merge is given a finite list of infinite lists, foldr merge can determine the first element of the merged list, and moves on to the next one. That way you can produce an arbitrary number of elements in the first case, but not a single one in the second case.


Let's expand foldr merge []:

foldr merge [] (xs0:xs1:xs2:...:[]) =
merge xs0 (merge xs1 (merge xs2 (merge xs3 ... [])))

Clearly, if (xs0:xs1:xs2:...:[]) is infinite, the "nested" calls to merge will form an infinite chain. But what about haskell being "lazy"? primes is also defined in terms of itself, yet it produces output? Well, there is actually a rule of foldr: it can produce output for infinite lists only if the function passed to foldr is not strict in its second argument - i.e. sometimes it can produce output without having to evaluate the result of foldr for the rest of the list.

The merge pattern-matches the second argument - that alone can cause non-termination - and uses a strict function <=, so merge is strict in the second argument, and the infinite chain will have to evaluate the first element of every list before the top level merge can produce any result.

Because merge is strict, and because merge is associative, you can - and should - use foldl' instead of foldr to merge the finite list of infinite lists.

6
  • Thanks, this perfectly answers my question!
    – Benji Wa
    Commented Apr 4, 2014 at 11:30
  • foldr or foldl' is secondary. Both won't help with the 2nd at all, and with the 1st, it's unclear which is better - foldr will use more stack to start producing but will build a better structure which will be working faster, with much less overhead.
    – Will Ness
    Commented Apr 4, 2014 at 19:31
  • @WillNess what makes the structure built by foldr better?
    – Sassa NF
    Commented Apr 4, 2014 at 20:13
  • I write about it in my answer (at the end). :)
    – Will Ness
    Commented Apr 4, 2014 at 20:16
  • @WillNess I think I do mention foldl' must be used only for finite lists of infinite lists (ie can't be used with variant 2), so I hope we are clear on that. I added the question on efficiency in your answer
    – Sassa NF
    Commented Apr 4, 2014 at 20:27
2

You can make both variants work, fairly easily. The technique involved is worth knowing.

Your code is equivalent to

primepowers n = 
  foldr merge [] 
      -- terminating:
 --   [[p^k | p <- primes]  | k <- [1..n]]  -- n infinite lists

      -- non terminating:
      [[p^k | k <- [1..n]]  | p <- primes]  -- infinite list of n-length lists

"Naturally, taking the minimum of an infinite list is non-terminating" is the truth, and only the truth, but it is not the whole truth, here.

Here, the infinite list primes is already sorted in increasing order of its elements. So the heads of the lists [p^k | k <- [1..n]] are sorted and increasing, and the lists themselves are sorted and increasing too. Based on this knowledge alone, we can right away produce the head element of the merged streams — the minimum of the infinite list of heads of all these lists — in O(1) time, without actually inspecting any of them, except the very first one (which is the answer, itself).

Your problem is thus solved by using the following function instead of merge, in the foldr expression:

imerge (x:xs) ys = x : merge xs ys

(as seen in the code by Richard Bird in the article by Melissa O'Neill). Now both variants will just work. imerge is non-strict in its 2nd argument and is naturally used with foldr, even with finite lists.

Using foldl instead of foldr is plain wrong with the 2nd variant, because foldl on an infinite list is non-terminating.

Using foldl with the 1st variant, though possible (since the list itself is finite), is suboptimal here: it will place the more frequently-producing streams at the bottom of the overall chain of merges, i.e. it will run slower than the one with foldr.

see also: folds on wikipedia.

7
  • what do you mean - "at the bottom of the overall chain of merges"? If merging has to inspect heads of all lists, why would it matter where the "most frequently-producing stream" is? I ceratinly learned from your answer, even though I realise it is sorted both ways, but the question was about the existing merge, so I didn't consider other ways.
    – Sassa NF
    Commented Apr 4, 2014 at 20:26
  • Each new number has to "percolate up" through all the binary merge nodes on its way to the top node. Because of laziness, after the very first number is produced, each binary merge node remembers the head of its argument which did not produce the number on previous step.
    – Will Ness
    Commented Apr 4, 2014 at 20:28
  • I am not sure what you mean. Can you illustrate it? It seems to me that in both cases the merge will use one list from "the" list, and one list constructed from preceding or succeeding folds. In both cases one needs to "percolate" the head of the list with the minimal element somewhere.
    – Sassa NF
    Commented Apr 4, 2014 at 20:31
  • I imagine to myself a degenerate tree of binary merge nodes. It is either skewed to the left (produced by foldl) or to the right (by foldr). e.g. (((a+b)+c)+d)+e. The top (here, rightmost) + will pull one of its inputs on each yield (except on the very first if will pull both). We know that numbers yielded by a will have to go through all the +s. In a+(...) they will have to go only through 1 such node.
    – Will Ness
    Commented Apr 4, 2014 at 20:33
  • this is discussed at haskell.org/haskellwiki/Prime_numbers#Linear_merging. Empirically it indeed shows if foldl is used instead of foldr, it becomes much slower.
    – Will Ness
    Commented Apr 4, 2014 at 20:39
1

The second version does not give you any output because the input is an infinite list of lists. If you think about it, foldr merge [] creates a sorted list from a list of lists, therefore the head element of the resulting list will be the minimum of all the head elements of the lists. Naturally, taking the minimum of an infinite list is non-terminating, so the function doesn't even get to the point when the first element of the result becomes available.

0

Neither of your functions will terminated

The first thing is that primes is an infinite list. That means the comprehension of the program dwells in its lazy evaluation

for the first function

primepowers :: Integer -> [Integer]
primepowers n = foldr (merge) [] (listOfPrimepowers n)    

listOfPrimepowers n = map (\x -> (map (\y -> y ^ x) primes)) [1..n]

will not terminated because. Even if the outer map is apply to a finite list [1..n] each \x consume by the inner map is apply on an infinite list primes.

The second function

primepowers :: Integer -> [Integer]
primepowers n = foldl (merge) [] (listOfPrimepowers n)

listOfPrimepowers n = map(\x -> (map(\y -> x ^ y) [1..n])) primes

will not terminate because the outer map is apply directly on an infinite list primes

1
  • 2
    I see your point. But I'm not interested in termination, I'm interested in some (infinite) output. The first version produces output while the second doesn't return any.
    – Benji Wa
    Commented Apr 4, 2014 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.