合并两个Streams(已排序)以获取最终排序的Stream

Question

例如,如何合并两个已排序整数的Streams？我认为这是非常基本的,但只是发现它根本不重要.下面的一个不是尾递归的,当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, ?)

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