An infinite list in haskell combined with fold * does not compute

Question

Let's say I want to get a sorted endless list of all forwards to exponent n .

I have a function to combine two sorted lists and a function that gives me prime numbers.

 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 returns the correct result, and the other does not. The only difference is that the first version displays the preprocessors in the same way as [[2,3,5,7, ...],[4,9,25,...]] , and the second version displays the simplest ones [[2,4,8],[3,9,27],[5,25,125], ...] . You see, infinity is on a different level in the list.

Do you have an explanation why the second function does not produce any output?

Answer 1

This is because foldr merge needs to look through all the lists to find the minimum element at the head of one of the lists. If foldr merge given an infinite list of end lists, foldr merge never calculate the first element of the list - it continues to search for the minimum element of the rest of the list of lists before it can compare it with the first element of the first list - 2 . On the other hand, if foldr merge given a finite list of infinite lists, foldr merge can determine the first element of the merged list and move on to the next. Thus, you can create an arbitrary number of elements in the first case, but not in the second case.

---

Let foldr merge [] unfold:

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

It is clear that if (xs0:xs1:xs2:...:[]) infinite, the "nested" merge calls form an infinite chain. But what about making haskell lazy? primes also defined in terms of himself, but does he make a conclusion? Well, actually there is a foldr rule: it can generate output for infinite lists only if the function passed to foldr is not strict in the second argument, that is, sometimes it can output the result without having to evaluate the result of foldr for the rest of the list.

The merge pattern corresponds to the second argument, which in itself can cause non-interruption, and uses the strict <= function, so merge is strict in the second argument, and an infinite chain will have to evaluate the first element of each list to the top level merge can produce any result.

Since merge is strict, and since merge is associative, you can - and should use foldl' instead of foldr to combine a finite list of infinite lists.

Answer 2

You can make both options work quite easily. The necessary equipment deserves attention.

Your code is equivalent

 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, the use of a minimum infinite list is infinite” is the truth, and only the truth, but that’s not the whole truth, here.

Here the endless list of primes already sorted in ascending order of its elements. Thus, the heads of the lists [p^k | k <- [1..n]] [p^k | k <- [1..n]] are sorted and incremented, and the lists themselves are also sorted and incremented. Based only on this knowledge, we can immediately create the header element of the combined threads; minimum endless list of chapters of all these lists; O (1) times, without checking any of them except the very first (this is the answer itself).

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

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

(as seen from Richard Byrd's code in Melissa O'Neill's article ). Now both options will work. imerge not strict in the second argument and, of course, is used with foldr , even with trailing lists.

Using foldl instead of foldr is incorrect in the second option, because foldl in an infinite list is not final.

Using foldl with the 1st option, although it is possible (since the list itself is finite), it is suboptimal here: it will place the more frequently occurring flows at the bottom of the general merger chain, i.e. it will run slower than foldr .

see also: creases on wikipedia .

Answer 3

The second version does not give you any output, because the input is an endless list of lists. If you think about it, foldr merge [] creates a sorted list from the list of lists, so the title element of the resulting list will be minimal for all the title elements of the lists. Naturally, the use of the minimum of the infinite list is not final, so the function does not even hit the point when the first element of the result becomes available.

Answer 4

None of your functions will be completed.

The first thing primes is an endless list. This means that understanding the program dwells on lazy assessment

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 be completed because. Even if the external map is applied to the final list [1..n], each \x consumed by the internal map is applied to the infinite list of primes .

Second function

 primepowers :: Integer -> [Integer] primepowers n = foldl (merge) [] (listOfPrimepowers n) listOfPrimepowers n = map(\x -> (map(\y -> x ^ y) [1..n])) primes 

will not end because the external map is applied directly to the infinite primes list