Java 8: streams and the Sieve of Eratosthenes

Question

The Sieve of Eratosthenes can be implemented very neatly in Haskell, using laziness to generate an infinite list and then remove all multiples of the head of the list from its tail:

primes :: [Int]
primes = sieve [2..]
sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x > 0]

I'm trying to learn about using streams in Java 8, but I figure out if there's a way of achieving the same result in Java as the Haskell code above. If I treat a Haskell lazy list as equivalent to a Java stream, it seems that I need to take a stream headed by 2 and produce a new stream with all multiples of 2 removed, and then take that stream and produce a new stream with all multiples of 3 removed, and...

And I have no idea how to proceed.

Is there any way of doing this, or am I deluding myself when I try to think of Java streams as comparable to Haskell lists?

Answer 1

Sure, it is possible, but greatly complicated by the fact that Java streams have no simple way of being decomposed into their head and their tail (you can easily get either one of these, but not both since the stream will already have been consumed by then - sounds like someone could use linear types...).

The solution, is to keep a mutable variable around. For instance, that mutable variable can be the predicate that tests whether a number is a multiple of any other number seen so far.

import java.util.stream.*;
import java.util.function.IntPredicate;

public class Primes {

   static IntPredicate isPrime = x -> true;
   static IntStream primes = IntStream
                               .iterate(2, i -> i + 1)
                               .filter(i -> isPrime.test(i))
                               .peek(i -> isPrime = isPrime.and(v -> v % i != 0));

   public static void main(String[] args) {
      // Print out the first 10 primes.
      primes.limit(10)
            .forEach(p -> System.out.println(p));

   }
}

Then, you get the expected result:

$ javac Primes.java
$ java Primes
2
3
5
7
11
13
17
19
23
29