Merge two Streams (ordered) to get a final sorted Stream

Question

For example, how to merge two Streams of sorted Integers? I thought it's very basic, but just found it's non trivial at all. The below one is not tail-recursive and it will stack-overflow when the Streams are large.

def merge(as: Stream[Int], bs: Stream[Int]): Stream[Int] = {
  (as, bs) match {
    case (Stream.Empty, bss) => bss
    case (ass, Stream.Empty) => ass
    case (a #:: ass, b #:: bss) =>
      if (a < b) a #:: merge(ass, bs)
      else b #:: merge(as, bss)
  }
}

We may want to turn it into a tail-recursive one by introducing a accumulator. However, if we pre-pend the accumulator, we will only get a stream of reversed order; if we append the accumulator with concatenation (#:::), it's NOT lazy (strict) any more.

What could be the solution here? Thanks

Answer 1

Turning a comment into an answer, there's nothing wrong with your merge.

It's not recursive at all - any one call to merge returns a new Stream without any other call to merge. a #:: merge(ass, bs) return a stream with first element a and where merge(ass, bs) will be called to evaluate the rest of the stream when required.

So

val m = merge(Stream.from(1,2), Stream.from(2, 2))
//> m  : Stream[Int] = Stream(1, ?)
m.drop(10000000).take(1)
//> res0:     scala.collection.immutable.Stream[Int] = Stream(10000001, ?)

works just fine. No stack overflow.