Scala的懒惰排序算法

Question

在Scala中能否做到这种事情？

- Mahesh

---

在我看来，一个问题应该是自包含的。提供更多细节的链接可以接受，但在这里引用两行Haskell代码不会太困难。 - user unknown

Answer 1

def quicksort[A](xs: Stream[A])(implicit o: Ordering[A]): Stream[A] = {
  import o._ 
  if (xs.isEmpty) xs else {
      val (smaller, bigger) = xs.tail.partition(_ < xs.head)
      quicksort(smaller) #::: xs.head #:: quicksort(bigger)
  }
}

也可以使用视图，但速度会慢得多：

def quicksort[A](xs: List[A])(implicit o: Ordering[A]) = {
  import o._
  def qs(xs: SeqView[A, List[A]]): SeqView[A, Seq[_]] = if (xs.isEmpty) xs else {
    val (smaller, bigger) = xs.tail.partition(_ < xs.head)
    qs(smaller) ++ (xs.head +: qs(bigger))
  }
  qs(xs.view)
}

- Daniel C. Sobral

---

@Daniel：我们可以将第一行替换为 quicksort[A <% Ordering[A]](xs: List[A]) = { 吗？ - Aymen

@Aymen，“Ordering”不如“Ordered”灵活。除此之外，是的，并且去掉第二行的“import”。 - Daniel C. Sobral

@Daniel：我认为SeqView不是懒加载。在其中放置一个计数器并查看。 - Walter Chang

为什么Stream.scala（和SeqView？）中的'sorted'，'sortBy'，'sortWith'等实现不使用这种惰性排序（或类似的实现）？还是有方法可以只使用库内置函数进行惰性排序吗？'sorted'不是一个“转换器”吗？文档说Stream“惰性地实现了所有转换器方法”，但据我所知，在这里似乎并非如此？ - nairbv

@Brian 这不是实现，因为没有人编写它，也没有人提交它，也没有人要求它。有人可能会说sorted是一个转换方法，但我猜想只有能够转换_值_的方法被认为是转换器。 - Daniel C. Sobral

Answer 2

是的！

Scala支持“lazy vals”作为一种推迟计算值直到实际使用的方式。Scala 2.8库的大部分都能够处理延迟定义的集合。

- Kevin Wright

---

这不回答所问的问题。 - Hui Wang