Scala中懒惰的迭代器？

Question

我已经在haskell中读到了,在对迭代器进行排序时,它只根据需要计算qsort的大小,以返回在生成的迭代器上实际计算的值的数量(即,它是懒惰的,即,一旦它完成了LHS第一个数据透镜可以返回一个值,它可以在迭代器上调用"next"时提供一个值,而不是继续旋转,除非再次调用next.

例如,在haskell中,head(qsort list)是O(n).它只是在列表中找到最小值,并且不会对列表的其余部分进行排序,除非访问其余结果qsort list.

有没有办法在Scala中执行此操作？我想在集合上使用sortWith,但只能根据需要进行排序,这样我就可以使用mySeq.sortWith(<).take(3)并且不需要完成排序操作.

我想知道是否可以以懒惰的方式使用其他排序函数(如sortBy),以及如何确保懒惰,以及如何查找有关何时对Scala中的排序进行懒惰评估的任何其他文档.

更新/编辑:我正在寻找使用sortWith等标准排序函数的方法.我宁愿不必实现我自己的quicksort版本只是为了得到懒惰的评价.不应该将它构建到标准库中,至少对于支持懒惰的Stream这样的集合？

Answer 1

我使用Scala的优先级队列实现来解决这种部分排序问题:

import scala.collection.mutable.PriorityQueue

val q = PriorityQueue(1289, 12, 123, 894, 1)(Ordering.Int.reverse)

现在我们可以致电dequeue:

scala> q.dequeue
res0: Int = 1

scala> q.dequeue
res1: Int = 12

scala> q.dequeue
res2: Int = 123

它的成本O(n)建立队列,并O(k log n)采取第一k要素.

不幸的是PriorityQueue,不按优先级顺序迭代,但编写一个调用的迭代器并不太难dequeue.