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

<p>Neither, actually -- it's a different technical term. </p>

<p>The type of streams of natural numbers can be interpreted as the final coalgebra for the functor $F(X) \triangleq \mathbb{N} \times X$. That is, define the category of $F$-algebras as follows:</p>

<ul>
<li><p>Objects are pairs $(X, \alpha)$, where $X$ is a set and $\alpha : X \to F(X)$ is a coalgebra for $F$. In this case, $\alpha : X \to \mathbb{N} \times X$. </p>

<p>Loosely speaking, you can think of $X$ as a representation type for a datatype which supports a stream interface, by letting you get the head and the tail of any $x \in X$ by calling $\alpha$. </p></li>
<li><p>Morphisms between objects $(X, \alpha)$ and $(Y, \beta)$ are those functions between sets $f : X \to Y$, which additionally respect the coalgebra structure. That is, we want $f; \beta = \alpha; F(f)$. </p></li>
</ul>

<p>Then, the type of streams is a final object in this category. That is, it's a set $(\mathrm{Stream}, \mathsf{cons})$, with the property that for every $(X, \alpha : X \to \mathbb{N} \times X)$, there is a unique map $X \to \mathrm{Stream}$. </p>

<p>The existence and uniqueness of that terminal map can be seen as a <em>principle of definition</em> for streams -- it says that you can take anything that "supports the stream interface", and then use it define an actual stream by using it only to produce the successive elements of the stream. In functional programming terms, this says that if you have a function <code>f : X → ℕ × X</code>, then the following corecursive definition is well-founded:</p>

<pre><code>build : X → Stream
build x = fst (f x) : build (snd (f x))
</code></pre>

<p>We can parameterize over the function <code>f</code> to get the <code>unfold</code> operator of functional programming.</p>

<pre><code>unfold : (X → ℕ × X) → X → Stream
unfold f x = fst (f x) : unfold f (snd (f x))
</code></pre>

<p>Definitions following the pattern of <code>build</code> are called "productive", since they are guaranteed to let you produce the corecursive data structure to any depth you desire --- even though the data structure is potentially infinite, you are guaranteed to reach any finite prefix in finite time. In this case, the intuition is that every recursive call is guarded by an application of the cons constructor <code>:</code>, and so repeatedly unfolding the definition yields ever more elements of the stream. </p>

<p>Let's see how the <code>merge'</code> function in your example code fits this pattern:</p>

<pre><code>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)
</code></pre>

<p>Notice that the generating type $X$ is $\mathtt{Stream} \times \mathtt{Stream}$, and we can define a function $f : (\mathtt{Stream} \times \mathtt{Stream}) \to \mathbb{N} \times \mathtt{Stream} \times \mathtt{Stream}$ as follows:</p>

<pre><code>f (x:xs, y:ys) | x &lt; y  = (x, (xs, y:ys))
               | x == y = (x, (xs,   ys))
               | x &gt; y  = (y, (x:xs, ys)) 
</code></pre>

<p>and then define <code>merge'</code> as:</p>

<pre><code>merge' = unfold f 
</code></pre>

CC BY-SA 3.0
2013-05-28T08:14:48.257Z
2013-05-28T11:15:49.587Z
2013-05-28T11:15:49.587Z
Neel Krishnaswami
<p>Productive here just means that it isn't stuck.</p>

<p>An unorthodox (seemingly <em>impredicative</em> ) formulation of the sieve of Eratosthenes is </p>

<p>&nbsp; &nbsp; &nbsp; <strong>S</strong> = {<em>n</em> : <em>n</em> &in; <strong>N</strong>, <em>n</em> &gt; 1} \ <strong>&bigcup;</strong><sub><em>p</em> &in; <strong>S</strong></sub> { <em>p q</em> :  <em>q</em> &in; <strong>N</strong>, <em>q</em> &ge; <em>p</em> }</p>

<hr>

<p>The following code is stuck, reflecting the above definition more or less verbatim:</p>



<pre><code>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..])
</code></pre>

<p>because <code>primes</code> list isn't primed with any initial data, so we get unbounded recursion. Asking <code>take 10 primes</code> produces no output (GHCi actually closes).</p>

<hr>

<p>The following is also stuck (or blows up, whatever you prefer to call it):</p>

<pre><code>primes = (2:) . gaps 3 . foldr (\p r-&gt; union [p*p, p*p+p..] r) [] $ primes
</code></pre>

<p>because each <code>union</code> demands to know the head of further results on its right, to produce <em>its</em> results. Asking <code>take 10 primes</code> produces <code>[2,</code> and then no output (GHCi will actually close itself on this <em>"racing to the bottom"</em> ).</p>

<hr>

<p>But this</p>

<pre><code>primes = (2:) . gaps 3 . foldr (\p r-&gt; p*p : union [p*p+p, p*p+2*p..] r) [] $ primes
</code></pre>

<p>works fine, because now getting the <em>head</em> of the further results doesn't trigger the next <code>union</code> call <em>right away</em>.</p>

<hr>

<p><a href="https://stackoverflow.com/a/16380903/849891">On SO you ask</a> how one could come up with such definition. </p>

<p>You could <a href="http://gist.github.com/WillNess/6040471#file-turner-s-to-bird-s-hs" rel="nofollow noreferrer">start with Turner's sieve</a>,</p>

<pre><code>primes = sieve [2..]
sieve (x:xs) = x : sieve [y | y&lt;- xs, rem y x /= 0]
</code></pre>

<p>then turn it into an <em>optimal</em> trial division sieve, by postponing the filters creation to the right moment, </p>

<pre><code>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]
</code></pre>

<p>then make it a kind of the sieve of Eratosthenes,</p>

<pre><code>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
</code></pre>

<p>The last step is to realize that <code>(...(((xs-a)-b)-c)-...) == xs - (a+(b+(c+(...))))</code>. <sub>(And the <em>next</em> step, that <a href="http://www.haskell.org/haskellwiki/Prime_numbers#Tree_merging" rel="nofollow noreferrer"><code>(a+(b+(c+(...)))) == a + ( (b+c) + ( ((d+e)+(f+g)) + ( ... )))</code></a>.)</sub></p>

<p>(or, it could <a href="http://www.haskell.org/pipermail/haskell-cafe/2007-July/028235.html" rel="nofollow noreferrer">"dawn on" you</a>).</p>

<p>(<em>edit:</em>) one more way is to tweak <em>your</em> SO code actually. :) with <a href="https://gist.github.com/WillNess/5659214#file-primesa-lhs" rel="nofollow noreferrer">just some minor tweaks</a> it becomes the very nice</p>

<pre><code>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 ..])
</code></pre>

<p>(though not properly postponed at all) which is finally fixed with</p>

<pre><code>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
</code></pre>

<p>as can be seen, your <code>sieve</code> is what I called <code>gaps</code> above.</p>

CC BY-SA 3.0
2013-05-28T04:48:47.107Z
Thanks! It may take me at least a day to absorb this properly.
minopret
CC BY-SA 3.0
2013-05-27T11:27:16.237Z
2015-12-28T11:47:52.570Z
2017-05-23T12:40:09.333Z
Will Ness
<p>M.E. O'Neill in the Epilogue of "The Genuine Sieve of Eratosthenes" (preprint <a href="http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf" rel="nofollow">http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf</a> DOI 10.1017/S0956796808007004) quotes Richard Bird that "<em>union</em> is defined in the way it is in order to be a productive function."</p>

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

<p>The function <em>union</em> is defined there in the following Haskell code:</p>

<pre><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
</code></pre>

<p>I haven't learned about productive sets. If it's helpful for understanding this point, I will.</p>

CC BY-SA 3.0
2013-05-02T22:59:38.780Z
Any suggestions for improvement? I imagined someone would answer this at a glance.
minopret
CC BY-SA 3.0
2013-05-03T11:28:23.063Z
We aren't that fast, I'm afraid. At a glance, you won't need to learn about productive sets. What Bird means is that in order to capture this union of infinite sets lazily, the function needs to produce its elements on demand, in the right order (i.e. interleave the individual heads properly).
Klaus Draeger
CC BY-SA 3.0
2013-05-03T14:23:52.510Z
Thanks @KlausDraeger for your comment and your warm welcome.
minopret
CC BY-SA 3.0
2013-05-05T03:06:07.297Z
For whom it may interest, there is now an account of my struggle to learn and use this insight [here](http://stackoverflow.com/questions/16271592) on Stack Overflow. So, I suppose that in Bird's sense here, a function that is _not_ "productive" is one that alternatively could be said to produce "bottom" (http://www.haskell.org/haskellwiki/Bottom).
minopret
CC BY-SA 3.0
2013-05-27T13:30:29.880Z
"Productive function" in functional programming has nothing to do with productive or creative sets in recursion theory. It's just a coincidence.
sdcvvc
<primes><recursion>
Does "Productive function" mean just that in ME O'Neill, The Genuine Sieve of Eratosthenes?
minopret
# Does "Productive function" mean just that in ME O'Neill, The Genuine Sieve of Eratosthenes?

(Asked by: username_0 on 2013-05-02)

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 <- primes]

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

(x:xs) `minus` (y:ys) | x< y = x:(xs `minus` (y:ys))
                      | x==y = xs `minus` ys
                      | x> y = (x:xs) `minus` ys

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

    merge' (x:xs) (y:ys) | x< y = x:merge' xs (y:ys)
                         | x==y = x:merge' xs ys
                         | x> y = y:merge' (x:xs) ys

I haven't learned about productive sets. If it's helpful for understanding this point, I will.

**Tags:** primes, recursion

> **Comments:**
> **username_0**: Any suggestions for improvement? I imagined someone would answer this at a glance.  
> **username_1**: We aren't that fast, I'm afraid. At a glance, you won't need to learn about productive sets. What Bird means is that in order to capture this union of infinite sets lazily, the function needs to produce its elements on demand, in the right order (i.e. interleave the individual heads properly).  
> **username_0**: Thanks @KlausDraeger for your comment and your warm welcome.  
> **username_0**: For whom it may interest, there is now an account of my struggle to learn and use this insight [here](http://stackoverflow.com/questions/16271592) on Stack Overflow. So, I suppose that in Bird's sense here, a function that is _not_ "productive" is one that alternatively could be said to produce "bottom" (http://www.haskell.org/haskellwiki/Bottom).  
> **username_2**: "Productive function" in functional programming has nothing to do with productive or creative sets in recursion theory. It's just a coincidence.  

---

## 2 answers

### Answer by username_4 on 2013-05-27. Score: 7 | Accepted answer

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(
then make it a kind of the sieve of Eratosthenes,
primes = 2 : sieve primes [3..]
sieve (p:ps) xs | (h,t) <- span( 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.

> **Comments:**
> **username_0**: Thanks! It may take me at least a day to absorb this properly.  

---

### Answer by username_3 on 2013-05-28. Score: 7

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

Neither, actually -- it's a different technical term. 
The type of streams of natural numbers can be interpreted as the final coalgebra for the functor $F(X) \triangleq \mathbb{N} \times X$. That is, define the category of $F$-algebras as follows:

Objects are pairs $(X, \alpha)$, where $X$ is a set and $\alpha : X \to F(X)$ is a coalgebra for $F$. In this case, $\alpha : X \to \mathbb{N} \times X$. 
Loosely speaking, you can think of $X$ as a representation type for a datatype which supports a stream interface, by letting you get the head and the tail of any $x \in X$ by calling $\alpha$. 
Morphisms between objects $(X, \alpha)$ and $(Y, \beta)$ are those functions between sets $f : X \to Y$, which additionally respect the coalgebra structure. That is, we want $f; \beta = \alpha; F(f)$. 

Then, the type of streams is a final object in this category. That is, it's a set $(\mathrm{Stream}, \mathsf{cons})$, with the property that for every $(X, \alpha : X \to \mathbb{N} \times X)$, there is a unique map $X \to \mathrm{Stream}$. 
The existence and uniqueness of that terminal map can be seen as a principle of definition for streams -- it says that you can take anything that "supports the stream interface", and then use it define an actual stream by using it only to produce the successive elements of the stream. In functional programming terms, this says that if you have a function f : X → ℕ × X, then the following corecursive definition is well-founded:
build : X → Stream
build x = fst (f x) : build (snd (f x))

We can parameterize over the function f to get the unfold operator of functional programming.
unfold : (X → ℕ × X) → X → Stream
unfold f x = fst (f x) : unfold f (snd (f x))

Definitions following the pattern of build are called "productive", since they are guaranteed to let you produce the corecursive data structure to any depth you desire --- even though the data structure is potentially infinite, you are guaranteed to reach any finite prefix in finite time. In this case, the intuition is that every recursive call is guarded by an application of the cons constructor :, and so repeatedly unfolding the definition yields ever more elements of the stream. 
Let's see how the merge' function in your example code fits this pattern:
merge' (x:xs, y:ys) | x< y = x:merge' (xs, y:ys)
                    | x==y = x:merge' (xs,   ys)
                    | x> y = y:merge' (x:xs, ys)

Notice that the generating type $X$ is $\mathtt{Stream} \times \mathtt{Stream}$, and we can define a function $f : (\mathtt{Stream} \times \mathtt{Stream}) \to \mathbb{N} \times \mathtt{Stream} \times \mathtt{Stream}$ as follows:
f (x:xs, y:ys) | x < y  = (x, (xs, y:ys))
               | x == y = (x, (xs,   ys))
               | x > y  = (y, (x:xs, ys)) 

and then define merge' as:
merge' = unfold f


---

