6

Is it possible to do this sort of thing in Scala?

Community
  • 1
  • 1
Mahesh
  • 69
  • 2
  • 5
    IMHO, a question should be self contained. Links for more details are okay, but citing two lines of haskell-code here wouldn't be too much work. – user unknown May 11 '11 at 18:47

2 Answers2

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

It can be done with views as well, though it's bound to be much slower:

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
  • 295,120
  • 86
  • 501
  • 681
  • Thanks but I would like to see the list-views implementation as well. – Mahesh Apr 22 '10 at 16:08
  • @Mahesh The view implementation turns out to be tougher than I first imagined. I'll keep trying to see if something works. – Daniel C. Sobral Apr 22 '10 at 21:36
  • @Mahesh Ok, got the problem ironed out. I was forgetting the `.head` on the concatenation line... Silly me. – Daniel C. Sobral Apr 22 '10 at 22:31
  • @Daniel: can we replace the first line with `quicksort[A <% Ordering[A]](xs: List[A]) = {` ? – Aymen Jul 29 '10 at 07:55
  • @Aymen An `Ordering` is not as flexible as an `Ordered`. Other than that, yes, and get rid of the `import` on the second line. – Daniel C. Sobral Aug 01 '10 at 16:45
  • @Daniel: I don't think the SeqView one is lazy. Stick a counter in there and see. – Walter Chang Apr 21 '11 at 05:50
  • Where can I find documentation for the `#:::` operator ? – nairbv Sep 28 '12 at 12:17
  • @Brian Look at the [index](http://www.scala-lang.org/archives/downloads/distrib/files/nightly/docs/library/index.html#index.index-_). – Daniel C. Sobral Sep 28 '12 at 16:30
  • 1
    Why isn't this lazy sort (or something like it) the implementation used for `sorted`, `sortBy`, `sortWith`, etc in Stream.scala (and SeqView?). Or is it? Is there any way to just use library built-in functions to sort lazily? Isn't `sorted` a "transformer?" The documentation says Stream "implements all its transformer methods lazily," but that doesn't seem to be the case here as far as I can tell? – nairbv Oct 01 '12 at 11:37
  • @Brian This isn't the implementation because no one wrote it, no one submitted it, and no one asked for it. One could argue that `sorted` is a transformer method, but I'm guessing only methods that transform _values_ are considered transformers. – Daniel C. Sobral Oct 03 '12 at 00:02
0

Yes!

Scala supports "lazy vals" as a way to defer calculation of a value until it's actually used. Much of the Scala 2.8 library is capable of working with lazily-defined collections.

Kevin Wright
  • 49,540
  • 9
  • 105
  • 155