title: How do I lazily concatenate streams?
body: <p>I'm trying to implement a stream that uses another instance of itself in its implementation.  The stream has a few constant elements prepended (with IntStream.concat) to it, so this should work as long as the concatenated stream creates the non-constant part lazily.  I think using the <a href="https://docs.oracle.com/javase/8/docs/api/java/util/stream/StreamSupport.html#intStream-java.util.function.Supplier-int-boolean-" rel="noreferrer">StreamSupport.intStream overload taking a Supplier</a> with IntStream.concat (which <a href="https://docs.oracle.com/javase/8/docs/api/java/util/stream/IntStream.html#concat-java.util.stream.IntStream-java.util.stream.IntStream-" rel="noreferrer">"creates a lazily concatenated stream"</a>) should be lazy enough to only create the second spliterator when elements are demanded from it, but even creating the stream (not evaluating it) overflows the stack.  How can I lazily concatenate streams?</p>
  
  <hr>
  
  <p>I'm attempting to port the streaming prime number sieve from <a href="https://stackoverflow.com/a/10733621/3614835">this answer</a> into Java.  This sieve uses another instance of itself (<code>ps = postponed_sieve()</code> in the Python code).  If I break the initial four constant elements (<code>yield 2; yield 3; yield 5; yield 7;</code>) into their own stream, it's easy to implement the generator as a spliterator:</p>
  
  <pre><code>/**
   * based on https://stackoverflow.com/a/10733621/3614835
   */
  static class PrimeSpliterator extends Spliterators.AbstractIntSpliterator {
      private static final int CHARACTERISTICS = Spliterator.DISTINCT | Spliterator.IMMUTABLE | Spliterator.NONNULL | Spliterator.ORDERED | Spliterator.SORTED;
      private final Map&lt;Integer, Supplier&lt;IntStream&gt;&gt; sieve = new HashMap&lt;&gt;();
      private final PrimitiveIterator.OfInt postponedSieve = primes().iterator();
      private int p, q, c = 9;
      private Supplier&lt;IntStream&gt; s;
      PrimeSpliterator() {
          super(105097564 /* according to Wolfram Alpha */ - 4 /* in prefix */,
                  CHARACTERISTICS);
          //p = next(ps) and next(ps) (that's Pythonic?)
          postponedSieve.nextInt();
          this.p = postponedSieve.nextInt();
          this.q = p*p;
      }
  
      @Override
      public boolean tryAdvance(IntConsumer action) {
          for (; c &gt; 0 /* overflow */; c += 2) {
              Supplier&lt;IntStream&gt; maybeS = sieve.remove(c);
              if (maybeS != null)
                  s = maybeS;
              else if (c &lt; q) {
                  action.accept(c);
                  return true; //continue
              } else {
                  s = () -&gt; IntStream.iterate(q+2*p, x -&gt; x + 2*p);
                  p = postponedSieve.nextInt();
                  q = p*p;
              }
              int m = s.get().filter(x -&gt; !sieve.containsKey(x)).findFirst().getAsInt();
              sieve.put(m, s);
          }
          return false;
      }
  }
  </code></pre>
  
  <p>My first attempt at the primes() method returns an IntStream concatenating a constant stream with a new PrimeSpliterator:</p>
  
  <pre><code>public static IntStream primes() {
      return IntStream.concat(IntStream.of(2, 3, 5, 7),
              StreamSupport.intStream(new PrimeSpliterator()));
  }
  </code></pre>
  
  <p>Calling primes() results in a StackOverflowError because primes() always instantiates a PrimeSpliterator, but PrimeSpliterator's field initializer always calls primes().  However, there's an overload of StreamSupport.intStream that takes a Supplier, which should allow lazily creating the PrimeSpliterator:</p>
  
  <pre><code>public static IntStream primes() {
      return IntStream.concat(IntStream.of(2, 3, 5, 7),
              StreamSupport.intStream(PrimeSpliterator::new, PrimeSpliterator.CHARACTERISTICS, false));
  }
  </code></pre>
  
  <p>However, I instead get a StackOverflowError with a different backtrace (trimmed, as it repeats).  Note that the recursion is entirely in the call to primes() -- the terminal operation iterator() is never invoked on a returned stream.</p>
  
  <pre><code>Exception in thread "main" java.lang.StackOverflowError
      at java.util.stream.StreamSpliterators$DelegatingSpliterator$OfInt.&lt;init&gt;(StreamSpliterators.java:582)
      at java.util.stream.IntPipeline.lazySpliterator(IntPipeline.java:155)
      at java.util.stream.IntPipeline$Head.lazySpliterator(IntPipeline.java:514)
      at java.util.stream.AbstractPipeline.spliterator(AbstractPipeline.java:352)
      at java.util.stream.IntPipeline.spliterator(IntPipeline.java:181)
      at java.util.stream.IntStream.concat(IntStream.java:851)
      at com.jeffreybosboom.projecteuler.util.Primes.primes(Primes.java:22)
      at com.jeffreybosboom.projecteuler.util.Primes$PrimeSpliterator.&lt;init&gt;(Primes.java:32)
      at com.jeffreybosboom.projecteuler.util.Primes$$Lambda$1/834600351.get(Unknown Source)
      at java.util.stream.StreamSpliterators$DelegatingSpliterator.get(StreamSpliterators.java:513)
      at java.util.stream.StreamSpliterators$DelegatingSpliterator.estimateSize(StreamSpliterators.java:536)
      at java.util.stream.Streams$ConcatSpliterator.&lt;init&gt;(Streams.java:713)
      at java.util.stream.Streams$ConcatSpliterator$OfPrimitive.&lt;init&gt;(Streams.java:789)
      at java.util.stream.Streams$ConcatSpliterator$OfPrimitive.&lt;init&gt;(Streams.java:785)
      at java.util.stream.Streams$ConcatSpliterator$OfInt.&lt;init&gt;(Streams.java:819)
      at java.util.stream.IntStream.concat(IntStream.java:851)
      at com.jeffreybosboom.projecteuler.util.Primes.primes(Primes.java:22)
      at com.jeffreybosboom.projecteuler.util.Primes$PrimeSpliterator.&lt;init&gt;(Primes.java:32)
      at com.jeffreybosboom.projecteuler.util.Primes$$Lambda$1/834600351.get(Unknown Source)
      at java.util.stream.StreamSpliterators$DelegatingSpliterator.get(StreamSpliterators.java:513)
      at java.util.stream.StreamSpliterators$DelegatingSpliterator.estimateSize(StreamSpliterators.java:536)
      at java.util.stream.Streams$ConcatSpliterator.&lt;init&gt;(Streams.java:713)
      at java.util.stream.Streams$ConcatSpliterator$OfPrimitive.&lt;init&gt;(Streams.java:789)
      at java.util.stream.Streams$ConcatSpliterator$OfPrimitive.&lt;init&gt;(Streams.java:785)
      at java.util.stream.Streams$ConcatSpliterator$OfInt.&lt;init&gt;(Streams.java:819)
      at java.util.stream.IntStream.concat(IntStream.java:851)
      at com.jeffreybosboom.projecteuler.util.Primes.primes(Primes.java:22)
  </code></pre>
  
  <p>How can I concatenate streams lazily enough to allow a stream to use another copy of itself in its implementation?</p>