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

Question

例如，如何合并两个已排序的整数流？我认为这是非常基本的，但只是发现它根本不是微不足道的。下面的不是尾递归的，当流很大时它会堆栈溢出。

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

将评论转化为答案，您的合并没有任何问题。

它根本不是递归的 - 任何对合并的调用都会返回一个新的流，而没有任何其他对合并的调用。 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, ?)

工作得很好。没有堆栈溢出。