# 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 <- 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.

• Any suggestions for improvement? I imagined someone would answer this at a glance. May 2 '13 at 22:59
• 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). May 3 '13 at 11:28
• Thanks @KlausDraeger for your comment and your warm welcome. May 3 '13 at 14:23
• For whom it may interest, there is now an account of my struggle to learn and use this insight here 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" (haskell.org/haskellwiki/Bottom). May 5 '13 at 3:06
• "Productive function" in functional programming has nothing to do with productive or creative sets in recursion theory. It's just a coincidence. May 27 '13 at 13:30

Productive here just means that it isn't stuck.

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

S = {n : nN, n > 1} \ pS { p q : qN, qp }

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.

• Thanks! It may take me at least a day to absorb this properly. May 28 '13 at 4:48

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