Does "Productive function" mean just that in ME O'Neill, The Genuine Sieve of Eratosthenes? M.E. O'Neill in the Epilogue of "The Genuine Sieve of Eratosthenes" (preprint http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf DOI 10.1017/S0956796808007004) quotes Richard Bird that "union is defined in the way it is in order to be a productive function."

Is that the technical term referring to productive sets and creative sets, or is it just a manner of speaking?

The function union is defined there in the following Haskell code:

primes = 2:([3..] `minus` composites)
  where
    composites = union [multiples p | p &lt;- primes]

multiples n = map (n*) [n..]

(x:xs) `minus` (y:ys) | x&lt; y = x:(xs `minus` (y:ys))
                      | x==y = xs `minus` ys
                      | x&gt; y = (x:xs) `minus` ys

union = foldr merge []
  where
    merge (x:xs) ys = x:merge' xs ys

    merge' (x:xs) (y:ys) | x&lt; y = x:merge' xs (y:ys)
                         | x==y = x:merge' xs ys
                         | x&gt; y = y:merge' (x:xs) ys


I haven't learned about productive sets. If it's helpful for understanding this point, I will.
Productive here just means that it isn't stuck.

An unorthodox (seemingly impredicative ) formulation of the sieve of Eratosthenes is 

&nbsp; &nbsp; &nbsp; S = {n : n &in; N, n &gt; 1} \ &bigcup;p &in; S { p q :  q &in; N, q &ge; p }



The following code is stuck, reflecting the above definition more or less verbatim:



primes = gaps 2 $ foldr (\p r-&gt; union [p*p, p*p+p..] r) [] primes

union (x:xs) (y:ys) = case compare x y of            -- ~= sort ( (x:xs) ++ (y:ys) )
                        LT -&gt; x : union  xs (y:ys)
                        EQ -&gt; x : union  xs    ys
                        GT -&gt; y : union (x:xs) ys

gaps c (x:xs) | c &lt; 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-&gt; 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-&gt; 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&lt;- 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) &lt;- span(&lt;p*p)xs = h ++ sieve ps [y | y&lt;- 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) &lt;- span(&lt;p*p)xs = h ++ sieve ps (minus t [p*p, p*p+p ..])

minus (x:xs) (y:ys) = case compare x y of
                        LT -&gt; x : minus  xs (y:ys)
                        EQ -&gt;     minus  xs    ys
                        GT -&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-&gt; 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.