Productive here just means that it isn't stuck.
An unorthodox (seemingly impredicative ) formulation of the sieve of Eratosthenes is
S = {n : n ∈ N, n > 1} \ ⋃p ∈ S { p q : q ∈ N, q ≥ p }
The following code is stuck, reflecting the above definition more or less verbatim:
primes = gaps 2 $ foldr (\p r-> union [p*p, p*p+p..] r) [] primes
union (x:xs) (y:ys) = case compare x y of -- ~= sort ( (x:xs) ++ (y:ys) )
LT -> x : union xs (y:ys)
EQ -> x : union xs ys
GT -> y : union (x:xs) ys
gaps c (x:xs) | c < x = c : gaps (c+1) (x:xs) -- ~= [c,c+2..] \\ (x:xs)
| otherwise = gaps (c+1) xs -- when null((x:xs)\\[c,c+2..])
because primes
list isn't primed with any initial data, so we get unbounded recursion. Asking take 10 primes
produces no output (GHCi actually closes).
The following is also stuck (or blows up, whatever you prefer to call it):
primes = (2:) . gaps 3 . foldr (\p r-> union [p*p, p*p+p..] r) [] $ primes
because each union
demands to know the head of further results on its right, to produce its results. Asking take 10 primes
produces [2,
and then no output (GHCi will actually close itself on this "racing to the bottom" ).
But this
primes = (2:) . gaps 3 . foldr (\p r-> p*p : union [p*p+p, p*p+2*p..] r) [] $ primes
works fine, because now getting the head of the further results doesn't trigger the next union
call right away.
On SO you ask how one could come up with such definition.
You could start with Turner's sieve,
primes = sieve [2..]
sieve (x:xs) = x : sieve [y | y<- xs, rem y x /= 0]
then turn it into an optimal trial division sieve, by postponing the filters creation to the right moment,
primes = 2 : sieve primes [3..]
sieve (p:ps) xs | (h,t) <- span(<p*p)xs = h ++ sieve ps [y | y<- t, rem y p /= 0]
then make it a kind of the sieve of Eratosthenes,
primes = 2 : sieve primes [3..]
sieve (p:ps) xs | (h,t) <- span(<p*p)xs = h ++ sieve ps (minus t [p*p, p*p+p ..])
minus (x:xs) (y:ys) = case compare x y of
LT -> x : minus xs (y:ys)
EQ -> minus xs ys
GT -> minus (x:xs) ys
The last step is to realize that (...(((xs-a)-b)-c)-...) == xs - (a+(b+(c+(...))))
. (And the next step, that (a+(b+(c+(...)))) == a + ( (b+c) + ( ((d+e)+(f+g)) + ( ... )))
.)
(or, it could "dawn on" you).
(edit:) one more way is to tweak your SO code actually. :) with just some minor tweaks it becomes the very nice
primesA :: [Integer]
primesA = 2 : 3 : sieve 5 [9, 15 ..]
sieve p cs@(c : t)
| p == c = sieve (p + 2) t
| otherwise = p : sieve (p + 2) (union cs [p*p, p*p+2*p ..])
(though not properly postponed at all) which is finally fixed with
primesA = [2,3,5] ++ sieve 7 (foldr (\p r-> p*p : union [p*p+2*p, p*p+4*p ..] r)
[] $ tail primesA)
sieve p cs@(c : t)
| p == c = sieve (p + 2) t
| otherwise = p : sieve (p + 2) cs
as can be seen, your sieve
is what I called gaps
above.