Haskell - List comprehension with infinite lists

Question

This is the piece of code

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

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

which is equal to the mathematical expression {p^i | p is prime, 1 <= i <= n}.

prime returns an infinite list of prime numbers. What I am interested is in the evaluation of (1). These are my thoughts:

If we first just look at [ map (^i) primes | i <- [1..3] ] this would return an infinite list of [[2,3,5,7,9,...],...]. But as we know p^1 (p is prime) never ends, Haskell will never evaluate [p^2] and [p^3]. Is this just because it is an infinite list or because of lazy evaluation?

Let's carry on with merge: merge will return [2,3,5,7,9,11,...] because again we still have an infinite list or because of some other reason?

Now to foldr: foldr starts evaluating from back. Here with specifically ask for the rightmost element, which is a infinite list [p^3]. So the evaluation would be like this

merge (merge (merge [] [p^3]) [p^2]) [p^1]

But we should not forget that these lists are infinite, so how does Haskell deal with that fact?

Could anyone explain me the evaluation process of the above function?

Answer 1

The trick is to define it as

primepowers n = foldr (\(x:xs) r-> x:merge xs r) 
                      [] [ map (^i) primes | i <- [1..n] ]

^{(as seen in Richard Bird's code in the article O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes").}

The lists to the right of a current one all start with bigger numbers, there's no chance of their merged list ever producing a value smaller or equal to the current list's head, so it can be produced unconditionally.

That way it will also explore only as many of the internal streams as needed:

GHCi> let pps_list = [ map (^i) primes | i <- [1..42] ]
GHCi> :sprint pps_list
pps_list = _
GHCi> take 20 $ foldr (\(x:xs) r-> x:merge xs r) [] pps_list
[2,3,4,5,7,8,9,11,13,16,17,19,23,25,27,29,31,32,37,41]
GHCi> :sprint pps_list
pps_list = (2 : 3 : 5 : 7 : 11 : 13 : 17 : 19 : 23 : 29 : 31 : 37 :
            41 : _) :
           (4 : 9 : 25 : 49 : _) : (8 : 27 : 125 : _) : (16 : 81 : _) :
           (32 : 243 : _) : (64 : _) : _

---

To your question per se, foldr f z [a,b,c,...,n] = f a (f b (f c (... (f n z)...))) so (writing ps_n for map (^n) primes), your expression is equivalent to

merge ps (merge ps_2 (merge ps_3 (... (merge ps_n [])...)))
= merge ps r
     where r = merge ps_2 (merge ps_3 (... (merge ps_n [])...))

because you use merge as your combining function. Notice that the leftmost merge springs into action first, while the expression for r isn't even built yet (because its value wasn't yet needed - Haskell's evaluation is by need.)

Now, this merge demands the head value of both its first and second argument (as written, it actually checks the second argument first, for being []).

The first argument isn't the problem, but the second is the result of folding all the rest of the lists ("r" in foldr's combining function stands for "recursive result"). Thus, each element in the list will be visited and its head element forced - and all this just to produce one very first value, the head of the result list, by the leftmost merge call...

In my code, the combining function does not at first demand the head of its second argument list. That's what limits its exploration of the whole list of lists, makes it more economic in its demands, and thus more productive (it will even work if you just omit the n altogether).

---

Your example Haskell expression [ map (^i) primes | i <- [1..3] ] returns finite list of length 3, each element being an infinite list: [[2,3,5,7,11,...],[4,9,25,...],[8,27,125,...]] so foldr has no problem translating it into merge [2,3,5,7,11,...] (merge [4,9,25,...] (merge [8,27,125,..] [])):

foldr merge [] [ map (^i) primes | i <- [1..3] ]
= merge [2,3,5,7,11,...] (foldr merge [] [ map (^i) primes | i <- [2..3] ])
= merge [2,3,5,7,11,...] (merge [4,9,25,...] (foldr merge [] [ map (^i) primes | i <- [3..3] ]))
= merge [2,3,5,7,11,...] (merge [4,9,25,...] (merge [8,27,125,..] (foldr merge [] [])))
= merge [2,3,5,7,11,...] (merge [4,9,25,...] (merge [8,27,125,..] []))
= merge [2,3,5,7,11,...] (merge [4,9,25,...] [8,27,125,..])
= merge [2,3,5,7,11,...] (4:merge [9,25,...] [8,27,125,..])
= 2:merge [3,5,7,11,...] (4:merge [9,25,...] [8,27,125,..])
= 2:3:merge [5,7,11,...] (4:merge [9,25,...] [8,27,125,..])
= 2:3:4:merge [5,7,11,...] (merge [9,25,...] [8,27,125,..])
= 2:3:4:merge [5,7,11,...] (8:merge [9,25,...] [27,125,..])
= 2:3:4:5:merge [7,11,...] (8:merge [9,25,...] [27,125,..])
.....

As you can see, the rightmost inner list is examined first, because merge is strict in (i.e. demands to know) both its arguments, as explained above. For [ map (^i) primes | i <- [1..42] ] it would expand all 42 of them, and examine the heads of all of them, before producing even the head element of the result.

---

With the tweaked function, mg (x:xs) r = x:merge xs r, the evaluation proceeds as

foldr mg [] [ map (^i) primes | i <- [1..3] ]
= mg [2,3,5,7,11,...] (foldr mg [] [ map (^i) primes | i <- [2..3] ])
= 2:merge [3,5,7,11,...] (foldr mg [] [ map (^i) primes | i <- [2..3] ])
= 2:merge [3,5,7,11,...] (mg [4,9,25,...] (foldr mg [] [ map (^i) primes | i <- [3..3] ]))
= 2:merge [3,5,7,11,...] (4:merge [9,25,...] (foldr mg [] [ map (^i) primes | i <- [3..3] ]))
= 2:3:merge [5,7,11,...] (4:merge [9,25,...] (foldr mg [] [ map (^i) primes | i <- [3..3] ]))
= 2:3:4:merge [5,7,11,...] (merge [9,25,...] (foldr mg [] [ map (^i) primes | i <- [3..3] ]))
= 2:3:4:merge [5,7,11,...] (merge [9,25,...] (mg [8,27,125,..] (foldr mg [] [])))
= 2:3:4:merge [5,7,11,...] (merge [9,25,...] (8:merge [27,125,..] (foldr mg [] [])))
= 2:3:4:merge [5,7,11,...] (8:merge [9,25,...] (merge [27,125,..] (foldr mg [] [])))
= 2:3:4:5:merge [7,11,...] (8:merge [9,25,...] (merge [27,125,..] (foldr mg [] [])))
.....

so it starts producing the results much sooner, without expanding much of the inner lists. This just follows the definition of foldr,

foldr f z (x:xs) = f x (foldr f z xs)

where, because of the laziness, (foldr f z xs) is not evaluated right away if f does not demand its value (or a part of it, like its head).

Answer 2

The lists being merged are infinite, but that doesn't matter.

What matters is that you only have a finite number of lists being merged, and so to compute the next element of the merge you only need to perform a finite number of comparisons.

To compute the head of merge xs ys you only need to compute the head of xs and the head of ys. So by induction, if you have a finite tree of merge operations, you can compute the head of the overall merge in finite time.

Answer 3

[map (^i) primes | i <- [1..3]] returns just thunk. Nothing is evaluated for now. You could try this:

xs = [x | x <- [1..], error ""]

main = print $ const 0 xs

This program prints 0, so error "" wasn't evaluated here.

You can think about foldr being defined like this:

foldr f z  []    = z
foldr f z (x:xs) = f x (foldr f xs)

Then

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

evaluates like this (after it was forced):

merge thunk1 (merge thunk2 (merge thunk3 []))

where thunkn is a suspended computation of primes in n-th power. Now the first merge forces evaluation of thunk1 and merge thunk2 (merge thunk3 []), which are evaluated to weak head normal forms (whnf). Forcing merge thunk2 (merge thunk3 []) causes forcing thunk2 and merge thunk3 []. merge thunk3 [] reduces to thunk3 and then thunk3 is forced. So the expression becomes

merge (2 : thunk1') (merge (4 : thunk2') (8 : thunk3'))

Which, due to the definition of merge, reduces to

merge (2 : thunk1') (4 : merge thunk2' (8 : thunk3')

And again:

2 : merge thunk1' (4 : merge thunk2' (8 : thunk3')

Now merge forces thunk1', but not the rest of the expression, because it's already in whnf

2 : merge (3 : thunk1'') (4 : merge thunk2' (8 : thunk3)
2 : 3 : merge thunk1'' (4 : merge thunk2' (8 : thunk3')
2 : 3 : merge (5 : thunk1''') (4 : merge thunk2' (8 : thunk3')
2 : 3 : 4 : merge (5 : thunk1''') (merge thunk2' (8 : thunk3')
2 : 3 : 4 : merge (5 : thunk1''') (merge (9 : thunk2'') (8 : thunk3')
2 : 3 : 4 : merge (5 : thunk1''') (8 : merge (9 : thunk2'') thunk3')
2 : 3 : 4 : 5 : merge thunk1''' (8 : merge (9 : thunk2'') thunk3')
...

Intuitively, only those values become evaluated, that are needed. Read this for a better explanation.

---

You can also merge infinite list of infinite lists. The simplest way would be:

interleave (x:xs) ys = x : interleave ys xs

primepowers = foldr1 interleave [map (^i) primes | i <- [1..]]

The interleave function interleaves two infinite lists, for example, interleave [1,3..] [2,4..] is equal to [1..]. So take 20 primepowers gives you [2,4,3,8,5,9,7,16,11,25,13,27,17,49,19,32,23,121,29,125]. But this list is unordered, we can do better.

[map (^i) primes | i <- [1..]] reduces to

[[2,3,5...]
,[4,9,25...]
,[8,27,125...]
...
]

We have the precondition, that in every n-th list there are elements, that are smaller, than head of the (n+1)-th list. We can extract such elements from the first list (2 and 3 are smaller than 4), and now we have this:

[[5,7,11...]
,[4,9,25...]
,[8,27,125...]
...
]

The precondition doesn't hold, so we must fix this and swap the first list and the second:

[[4,9,25...]
,[5,7,11...]
,[8,27,125...]
...
]

Now we extract 4 and swap the first list and the second:

[[5,7,11...]
,[9,25,49...]
,[8,27,125...]
...
]

But the precondition doesn't hold, since there are elements in the second list (9), that are not smaller than the head of the third list (8). So we do the same trick again:

[[5,7,11...]
,[8,27,125...]
,[9,25,49...]
...
]

And now we can extract elements again. Repeating the process infinitely gives us ordered list of prime powers. Here is the code:

swap xs@(x:_) xss = xss1 ++ xs : xss2 where
    (xss1, xss2) = span ((< x) . head) xss 

mergeAll (xs:xss@((x:_):_)) = xs1 ++ mergeAll (swap xs2 xss) where
    (xs1, xs2) = span (< x) xs

primepowers = mergeAll [map (^i) primes | i <- [1..]]

For example, take 20 primepowers is equal to [2,3,4,5,7,8,9,11,13,16,17,19,23,25,27,29,31,32,37,41].

This is probably not the nicest way to obtaining ordered list of prime powers, but it's fairly easy one.

EDIT

Look at the Will Ness' answer for a better solution, which is both easier and nicer.

Answer 4

It is true that merge needs to completely scan its whole input lists to produce its whole output. However, the key point is that every element in the output depends only from finite prefixes of the input lists.

For instance, consider take 10 (map (*2) [1..]). To compute the first 10 elements, you do not need to examine the whole [1..]. Indeed, map will not scan the whole infinite list and "after that" start returning the output: if it behaved like that, it would simply hang on infinite lists. This "streaming" property of map is given by laziness and the map definition

map f [] = []
map f (x:xs) = x : map f xs

The last line reads "yield x, and then proceed with the rest", so the caller gets to inspect x before map produces its whole output. By comparison

map f xs = go xs []
  where go []     acc = acc
        go (x:xs) acc = go xs (acc ++ [f x])

would be another definition of map which would start generating its output only after its input has been consumed. It is equivalent on finite lists (performance aside), but not equivalent on infinite ones (hangs on infinite lists).

If you want to empirically test that your merge is indeed working lazily, try this:

take 10 $ merge (10:20:30:error "end of 1") (5:15:25:35:error "end of 2")

Feel free to play by changing the constants. You will see an exception being printed on screen, but only after a few list elements have already been produced by merge.