合并两个流(排序)以获得最终排序的流

Question

例如，如何合并两个排序整数流？我觉得这很基本，但我发现它一点也不琐碎。下面的不是尾部递归，当Streams很大时，它会发生堆栈溢出。

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)
  }
}

我们可能想通过引入累加器将它变成一个尾部递归。然而，如果我们预挂累加器，我们只会得到一个顺序相反的流；如果我们用串联（#：：）来附加累加器，它就不再是懒惰的（严格的）。

这里的解决方案是什么？感谢

Answer 1

将注释转化为答案，合并没有任何问题。

它根本不是递归的——任何一个合并调用都会返回一个新的Stream，而没有任何其他合并调用。a #:: merge(ass, bs)返回具有第一元素a的流，并且其中merge(ass, bs)将在需要时被调用以评估流的其余部分。

所以

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, ?)

效果很好。没有堆栈溢出。