Path: csiph.com!usenet.pasdenom.info!news.albasani.net!.POSTED!not-for-mail
From: Sebastian <news@seyweiler.dyndns.org>
Newsgroups: comp.lang.java.programmer
Subject: Java 8 Streams and Eratosthenes
Date: Tue, 04 Jun 2013 23:54:34 +0200
Organization: albasani.net
Lines: 103
Message-ID: <kolnme$g3e$1@news.albasani.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: news.albasani.net FyIusmb0qN8Z1Bhd6hKVsrfRKcwZOSdyk1YF7m9yY4zvSI53ynRwS87itnVdiO8G9IglaZfci3zvfyMoVldK8Q==
NNTP-Posting-Date: Tue, 4 Jun 2013 21:54:22 +0000 (UTC)
Injection-Info: news.albasani.net; logging-data="QkEg0dNJtS2M3QLr5ROsFWX07zEw7hM0CtTNOUn1frM5P5F3Np2udzvYvH6Uby7WdRSdQ4AlxIaTEmPk81jfQ8gwyPq1oyEJyYCC5ak9tWUgZ3ztIJk9BeHexhpwp2lw"; mail-complaints-to="abuse@albasani.net"
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; de; rv:1.9.2.15) Gecko/20110303 Thunderbird/3.1.9
Cancel-Lock: sha1:iJv2ca+P30hSY/fA6sqy9UuFilY=
Xref: csiph.com comp.lang.java.programmer:24289

Hello there,

I'd like to start an open discussion on issues involving the Streams
API. As an exercise, I have looked at generating the first n primes,
for some given n, using the sieve of Eratosthenes. It seemed a
plausible enough proposition, seeing that the sieve involves repeatedly
filtering a sequence of integers.

However, things were made difficult by the fact that Stream#findFirst()
is a terminal (and short-circuiting) operation, so I couldn't use it
to access the first stream element to incrementally build a result.
The solution shown below uses an additional storage for these elements,
and finds out which of the elements passing through the stream are new 
primes by counting them at each stage. This works, but it is certainly
not something to show your functional programming friends.

I'd be grateful for suggestions for improvement, or other solutions.
I'd also like to know how this could be enhanced to generate an
infinite stream of primes (i. e. when the upper bound n is unknown and
new filters may need to be generated on the fly). I could imagine a
solution if it were possible to "pipe" one stream into another, but that
doesn't seem to be possible.

Perhaps the lesson is that some things are best not done using
streams. I also include a Java7 while-loop version of the same below.
This is more concise, clearer and easily generalizes to an infinite
stream. (However, it is eager, not lazy, and would take some more effort
to convert to a lazy solution, probably involving Callbacks and perhaps
losing its conciseness.)

What are your opinions?

Best,
Sebastian

Code follows. This has been tested to compile and run with lambda b88.
======================================================================

public void primes(int n) {
   List<Integer> primes = new ArrayList<>();
   Stream<Integer> s = Stream.iterate(2, x -> x + 1);
   for (int i = 0; i < n; i++) {
     int k = i;
     Consumer<Integer> kthPrime = kthPrime(k, primes);
     s = s.peek(kthPrime).filter(x -> {int p = currPrime(k,primes);
                                       return x == p || x % p != 0;});
   }
   assert primes.isEmpty();
   s.limit(n).forEach(x -> System.out.print(x + " "));
   assert primes.size() == n;
}

  /**
   * Find the prime that is used in the kth filter. That is the kth prime
   * if it has been discovered yet, otherwise it is a smaller prime that
   * is currently passing throgh the stream and must be let through the
   * filter.
   * @param k the filter number
   * @param primes the list of primes
   * @return the largest prime with an index less than or equal to k
   */
private Integer currPrime(int k, List<Integer> primes) {
   return primes.get(min(k,primes.size()-1));
}

/**
  * Mark the kth prime number for reference in a subsequent filter.
  * @param k the prime number index
  * @param primes the list of primes
  * @return a consumer that puts the kth integer that comes its way
  * into the specified list of primes
  */
private Consumer<Integer> kthPrime(int k, List<Integer> primes) {
   return new Consumer<Integer>() {
     private int idx;

     @Override
     public void accept(Integer p) {
       if (idx > k) return;
       if (idx == k) primes.add(p);
       idx++;
     }
   };
}

/**
  * For comparison, here is a Java 7 version of the prime generator.
  * @param n limit on the number of primes
  */
public void primesJava7(int n) {
   List<Integer> primes = new ArrayList<>();
   int x = 2;
   while (primes.size() < n) {
     boolean isPrime = true;
     for (Iterator<Integer> it = primes.iterator();
          isPrime && it.hasNext();) {
       if (x % it.next() == 0) isPrime = false;
     }
     if (isPrime) primes.add(x);
     x++;
   }
   System.out.println(primes);
}