Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Any suggestions for improvement? I imagined someone would answer this at a glance. –  minopret May 2 '13 at 22:59
2  
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 May 3 '13 at 11:28
    
Thanks @KlausDraeger for your comment and your warm welcome. –  minopret 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). –  minopret May 5 '13 at 3:06
1  
"Productive function" in functional programming has nothing to do with productive or creative sets in recursion theory. It's just a coincidence. –  sdcvvc May 27 '13 at 13:30
add comment

2 Answers 2

up vote 7 down vote accepted

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} \ UpS { pq : 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
                        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)
              | otherwise =     gaps (c+1) xs        -- c==x

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

share|improve this answer
    
Thanks! It may take me at least a day to absorb this properly. –  minopret May 28 '13 at 4:48
add comment

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 
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.