Does "Productive function" mean just that in ME O'Neill, The Genuine Sieve of Eratosthenes?

Question

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.

Answer 1

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.

Answer 2

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