问题描述:

Java 8 introduced a Stream class that resembles Scala's Stream, a powerful lazy construct using which it is possible to do something like this very concisely:

`def from(n: Int): Stream[Int] = n #:: from(n+1)`

def sieve(s: Stream[Int]): Stream[Int] = {

s.head #:: sieve(s.tail filter (_ % s.head != 0))

}

val primes = sieve(from(2))

primes takeWhile(_ < 1000) print // prints all primes less than 1000

I wondered if it is possible to do this in Java 8, so I wrote something like this:

`IntStream from(int n) {`

return IntStream.iterate(n, m -> m + 1);

}

IntStream sieve(IntStream s) {

int head = s.findFirst().getAsInt();

return IntStream.concat(IntStream.of(head), sieve(s.skip(1).filter(n -> n % head != 0)));

}

IntStream primes = sieve(from(2));

Fairly simple, but it produces `java.lang.IllegalStateException: stream has already been operated upon or closed`

because both `findFirst()`

and `skip()`

are terminal operations on `Stream`

which can be done only once.

I don't really have to use up the stream twice since all I need is the first number in the stream and the rest as another stream, i.e. equivalent of Scala's `Stream.head`

and `Stream.tail`

. Is there a method in Java 8 `Stream`

that I can use to achieve this?

Thanks.

Even if you hadn’t the problem that you can’t split an `IntStream`

, you code didn’t work because you are invoking your `sieve`

method recursively instead of lazily. So you had an infinity recursion before you could query your resulting stream for the first value.

Splitting an `IntStream s`

into a head and a tail `IntStream`

(which has not yet consumed) is possible:

```
PrimitiveIterator.OfInt it = s.iterator();
int head = it.nextInt();
IntStream tail = IntStream.generate(it::next).filter(i -> i % head != 0);
```

At this place you need a construct of invoking `sieve`

on the tail lazily. `Stream`

does not provide that; `concat`

expects existing stream instances as arguments and you can’t construct a stream invoking `sieve`

lazily with a lambda expression as lazy creation works with mutable state only which lambda expressions do not support. If you don’t have a library implementation hiding the mutable state you have to use a mutable object. But once you accept the requirement of mutable state, the solution can be even easier than your first approach:

```
IntStream primes = from(2).filter(i -> p.test(i)).peek(i -> p = p.and(v -> v % i != 0));
IntPredicate p = x -> true;
IntStream from(int n)
{
return IntStream.iterate(n, m -> m + 1);
}
```

This will recursively create a filter but in the end it doesn’t matter whether you create a tree of `IntPredicate`

s or a tree of `IntStream`

s (like with your `IntStream.concat`

approach if it did work). If you don’t like the mutable instance field for the filter you can hide it in an inner class (but not in a lambda expression…).

You can essentially implement it like this:

```
static <T> Tuple2<Optional<T>, Seq<T>> splitAtHead(Stream<T> stream) {
Iterator<T> it = stream.iterator();
return tuple(it.hasNext() ? Optional.of(it.next()) : Optional.empty(), seq(it));
}
```

In the above example, `Tuple2`

and `Seq`

are types borrowed from jOOλ, a library that we developed for jOOQ integration tests. If you don't want any additional dependencies, you might as well implement them yourself:

```
class Tuple2<T1, T2> {
final T1 v1;
final T2 v2;
Tuple2(T1 v1, T2 v2) {
this.v1 = v1;
this.v2 = v2;
}
static <T1, T2> Tuple2<T1, T2> tuple(T1 v1, T2 v2) {
return new Tuple<>(v1, v2);
}
}
static <T> Tuple2<Optional<T>, Stream<T>> splitAtHead(Stream<T> stream) {
Iterator<T> it = stream.iterator();
return tuple(
it.hasNext() ? Optional.of(it.next()) : Optional.empty,
StreamSupport.stream(Spliterators.spliteratorUnknownSize(
it, Spliterator.ORDERED
), false)
);
}
```

The solution below does not do state mutations, except for the head/tail deconstruction of the stream.

The lazyness is obtained using IntStream.iterate. The class Prime is used to keep the generator state

```
import java.util.PrimitiveIterator;
import java.util.stream.IntStream;
import java.util.stream.Stream;
public class Prime {
private final IntStream candidates;
private final int current;
private Prime(int current, IntStream candidates)
{
this.current = current;
this.candidates = candidates;
}
private Prime next()
{
PrimitiveIterator.OfInt it = candidates.filter(n -> n % current != 0).iterator();
int head = it.next();
IntStream tail = IntStream.generate(it::next);
return new Prime(head, tail);
}
public static Stream<Integer> stream() {
IntStream possiblePrimes = IntStream.iterate(3, i -> i + 1);
return Stream.iterate(new Prime(2, possiblePrimes), Prime::next)
.map(p -> p.current);
}
}
```

The usage would be this:

```
Stream<Integer> first10Primes = Prime.stream().limit(10)
```

If you don't mind using 3rd party libraries cyclops-streams, I library I wrote has a number of potential solutions.

The StreamUtils class has large number of static methods for working directly with `java.util.stream.Streams`

including `headAndTail`

.

```
HeadAndTail<Integer> headAndTail = StreamUtils.headAndTail(Stream.of(1,2,3,4));
int head = headAndTail.head(); //1
Stream<Integer> tail = headAndTail.tail(); //Stream[2,3,4]
```

The Streamable class represents a replayable `Stream`

and works by building a lazy, caching intermediate data-structure. Because it is caching and repayable - head and tail can be implemented directly and separately.

```
Streamable<Integer> replayable= Streamable.fromStream(Stream.of(1,2,3,4));
int head = repayable.head(); //1
Stream<Integer> tail = replayable.tail(); //Stream[2,3,4]
```

cyclops-streams also provides a sequential `Stream`

extension that in turn extends jOOλ and has both `Tuple`

based (from jOOλ) and domain object (HeadAndTail) solutions for head and tail extraction.

```
SequenceM.of(1,2,3,4)
.splitAtHead(); //Tuple[1,SequenceM[2,3,4]
SequenceM.of(1,2,3,4)
.headAndTail();
```

Update per Tagir's request -> A Java version of the Scala sieve using `SequenceM`

```
public void sieveTest(){
sieve(SequenceM.range(2, 1_000)).forEach(System.out::println);
}
SequenceM<Integer> sieve(SequenceM<Integer> s){
return s.headAndTailOptional().map(ht ->SequenceM.of(ht.head())
.appendStream(sieve(ht.tail().filter(n -> n % ht.head() != 0))))
.orElse(SequenceM.of());
}
```

And another version via `Streamable`

```
public void sieveTest2(){
sieve(Streamable.range(2, 1_000)).forEach(System.out::println);
}
Streamable<Integer> sieve(Streamable<Integer> s){
return s.size()==0? Streamable.of() : Streamable.of(s.head())
.appendStreamable(sieve(s.tail()
.filter(n -> n % s.head() != 0)));
}
```

Note - neither `Streamable`

of `SequenceM`

have an Empty implementation - hence the size check for `Streamable`

and the use of `headAndTailOptional`

.

Finally a version using plain `java.util.stream.Stream`

```
import static com.aol.cyclops.streams.StreamUtils.headAndTailOptional;
public void sieveTest(){
sieve(IntStream.range(2, 1_000).boxed()).forEach(System.out::println);
}
Stream<Integer> sieve(Stream<Integer> s){
return headAndTailOptional(s).map(ht ->Stream.concat(Stream.of(ht.head())
,sieve(ht.tail().filter(n -> n % ht.head() != 0))))
.orElse(Stream.of());
}
```

Another update - a lazy iterative based on @Holger's version using objects rather than primitives (note a primitive version is also possible)

```
final Mutable<Predicate<Integer>> predicate = Mutable.of(x->true);
SequenceM.iterate(2, n->n+1)
.filter(i->predicate.get().test(i))
.peek(i->predicate.mutate(p-> p.and(v -> v%i!=0)))
.limit(100000)
.forEach(System.out::println);
```

To get head and tail you need a Lazy Stream implementation. Java 8 stream or RxJava are not suitable.

You can use for example LazySeq as follows.

Lazy sequence is always traversed from the beginning using very cheap first/rest decomposition (head() and tail())

LazySeq implements java.util.List interface, thus can be used in variety of places. Moreover it also implements Java 8 enhancements to collections, namely streams and collectors

```
package com.company;
import com.nurkiewicz.lazyseq.LazySeq;
public class Main {
public static void main(String[] args) {
LazySeq<Integer> ints = integers(2);
LazySeq primes = sieve(ints);
primes.take(10).forEach(p -> System.out.println(p));
}
private static LazySeq<Integer> sieve(LazySeq<Integer> s) {
return LazySeq.cons(s.head(), () -> sieve(s.filter(x -> x % s.head() != 0)));
}
private static LazySeq<Integer> integers(int from) {
return LazySeq.cons(from, () -> integers(from + 1));
}
}
```

Here is another recipe using the way suggested by Holger. It use RxJava just to add the possibility to use the take(int) method and many others.

```
package com.company;
import rx.Observable;
import java.util.function.IntPredicate;
import java.util.stream.IntStream;
public class Main {
public static void main(String[] args) {
final IntPredicate[] p={(x)->true};
IntStream primesStream=IntStream.iterate(2,n->n+1).filter(i -> p[0].test(i)).peek(i->p[0]=p[0].and(v->v%i!=0) );
Observable primes = Observable.from(()->primesStream.iterator());
primes.take(10).forEach((x) -> System.out.println(x.toString()));
}
}
```

My StreamEx library has now `headTail()`

operation which solves the problem:

```
public static StreamEx<Integer> sieve(StreamEx<Integer> input) {
return input.headTail((head, tail) ->
sieve(tail.filter(n -> n % head != 0)).prepend(head));
}
```

The `headTail`

method takes a `BiFunction`

which will be executed at most once during the stream terminal operation execution. So this implementation is lazy: it does not compute anything until traversal starts and computes only as much prime numbers as requested. The `BiFunction`

receives a first stream element `head`

and the stream of the rest elements `tail`

and can modify the `tail`

in any way it wants. You may use it with predefined input:

```
sieve(IntStreamEx.range(2, 1000).boxed()).forEach(System.out::println);
```

But infinite stream work as well

```
sieve(StreamEx.iterate(2, x -> x+1)).takeWhile(x -> x < 1000)
.forEach(System.out::println);
// Not the primes till 1000, but 1000 first primes
sieve(StreamEx.iterate(2, x -> x+1)).limit(1000).forEach(System.out::println);
```

There's also alternative solution using `headTail`

and predicate concatenation:

```
public static StreamEx<Integer> sieve(StreamEx<Integer> input, IntPredicate isPrime) {
return input.headTail((head, tail) -> isPrime.test(head)
? sieve(tail, isPrime.and(n -> n % head != 0)).prepend(head)
: sieve(tail, isPrime));
}
sieve(StreamEx.iterate(2, x -> x+1), i -> true).limit(1000).forEach(System.out::println);
```

It interesting to compare recursive solutions: how many primes they capable to generate.

**@John McClean solution ( StreamUtils)**

John McClean solutions are not lazy: you cannot feed them with infinite stream. So I just found by trial-and-error the maximal allowed upper bound (`17793`

) (after that StackOverflowError occurs):

```
public void sieveTest(){
sieve(IntStream.range(2, 17793).boxed()).forEach(System.out::println);
}
```

**@John McClean solution ( Streamable)**

```
public void sieveTest2(){
sieve(Streamable.range(2, 39990)).forEach(System.out::println);
}
```

Increasing upper limit above `39990`

results in StackOverflowError.

**@frhack solution ( LazySeq)**

```
LazySeq<Integer> ints = integers(2);
LazySeq primes = sieve(ints); // sieve method from @frhack answer
primes.forEach(p -> System.out.println(p));
```

Result: stuck after prime number = `53327`

with enormous heap allocation and garbage collection taking more than 90%. It took several minutes to advance from 53323 to 53327, so waiting more seems impractical.

**@vidi solution**

```
Prime.stream().forEach(System.out::println);
```

Result: StackOverflowError after prime number = `134417`

.

**My solution (StreamEx)**

```
sieve(StreamEx.iterate(2, x -> x+1)).forEach(System.out::println);
```

Result: StackOverflowError after prime number = `236167`

.

**@frhack solution ( rxjava)**

```
Observable<Integer> primes = Observable.from(()->primesStream.iterator());
primes.forEach((x) -> System.out.println(x.toString()));
```

Result: StackOverflowError after prime number = `367663`

.

**@Holger solution**

```
IntStream primes=from(2).filter(i->p.test(i)).peek(i->p=p.and(v->v%i!=0));
primes.forEach(System.out::println);
```

Result: StackOverflowError after prime number = `368089`

.

**My solution (StreamEx with predicate concatenation)**

```
sieve(StreamEx.iterate(2, x -> x+1), i -> true).forEach(System.out::println);
```

Result: StackOverflowError after prime number = `368287`

.

So three solutions involving predicate concatenation win, because each new condition adds only 2 more stack frames. I think, the difference between them is marginal and should not be considered to define a winner. However I like my first StreamEx solution more as it more similar to Scala code.

If you want to get head of a stream, just:

```
IntStream.range(1, 5).first();
```

If you want to get tail of a stream, just:

```
IntStream.range(1, 5).skip(1);
```

If you want to get both head and tail of a stream, just:

```
IntStream s = IntStream.range(1, 5);
int head = s.head();
IntStream tail = s.tail();
```

If you want to find the prime, just:

```
LongStream.range(2, n)
.filter(i -> LongStream.range(2, (long) Math.sqrt(i) + 1).noneMatch(j -> i % j == 0))
.forEach(N::println);
```

If you want to know more, go to get AbacusUtil

Declaration： I'm the developer of AbacusUtil.