Scala: make function polymorphic in data structure type

Question

So I have been learning Scala for the past month, and yesterday I was playing around in the REPL with simple sorting algorithms. Using the standard functional quicksort, it's easy to make a sort function polymorphic in the element type, but it got me thinking: what if I could make it polymorphic in the type of data structure as well? It's annoying to have separate functions for List,Vector,etc. Of course, I could have it just take a Seq[E], but then there seems to be no guarantee as to the underlying implementation of that Seq[E]. All the linear collections implement Seq, which has all the functions we need(filter, apply, and append) so we should be able to have one function that can sort all linear collections, right? I came up with the following code:

object QSort {
  def qsort[E, D[E] <: Seq[E]](s: D[E])(c: (E, E) => Int): D[E] = {
    if (s.length <= 1) s
    else {
      val pivot: E = s(s.length / 2)
      qsort[E, D](s.filter((x: E) => c(x, pivot) < 0))(c)
              .append(s.filter((x: E) => c(x, pivot) == 0))
              .append(qsort[E, D](s.filter((x: E) => c(x, pivot) > 0))(c))
    }
  }
}

which takes some data structure D[E] that is a subclass of Seq[E] and a comparator function and should apply a highly inefficient quicksort. However, the compiler says that when I call filter, there is a type mismatch since filter returns a Seq[E] and not a D[E]. Why does filter not return a D[E], and is this kind of polymorphism even actually possible?

"you could declare it to just take Seq[E], but then there would be no guarantee of ... something"? So, you declare it to that D[E] instead ... What kind of guarantee exactly does it provide in your view? — Dima
This sort of polymorphism is indeed possible. One way to do it is to use the Builder trait (and CanBuildFrom) as is done in other collections. The general idea is to sort, creating a new Seq, then create a Builder from the CanBuildFrom instance, then append the resulting Seq to the builder and return the result. Take a look at blog.bruchez.name/2012/08/…, for instance. — Phasmid

evan.oman evan.oman · Accepted Answer · 2017-01-02T09:12:13

I would highly reccomend reading more about CanBuildFrom but here is how it can be used for your problem:

scala> :pa
// Entering paste mode (ctrl-D to finish)

import scala.collection.generic.CanBuildFrom

object QSort {
    def qsort[E, D[E] <: Seq[E]]
        (s: D[E])(c: (E, E) => Int)
        (implicit cbf: CanBuildFrom[D[E], E, D[E]]): D[E] =
    {
        if (s.size <= 1)
            s
        else
        {
            val pivot: E = s(s.size / 2)

            (qsort(s.filter((x: E) => c(x, pivot) < 0))(c) ++
            s.filter((x: E) => c(x, pivot) == 0) ++
            qsort(s.filter((x: E) => c(x, pivot) > 0))(c)).to[D]
        }
    }
}

// Exiting paste mode, now interpreting.

import scala.collection.generic.CanBuildFrom
defined module QSort

scala> val l = List(1, -10, 12, 2)
l: List[Int] = List(1, -10, 12, 2)

scala> val c = (a: Int, b:Int) => if (a == b) 0 else if (a < b) 1 else -1
c: (Int, Int) => Int = <function2>

scala> QSort.qsort(l)(c)
res0: List[Int] = List(12, 2, 1, -10)

scala> QSort.qsort(l.toSeq)(c)
res1: scala.collection.immutable.Seq[Int] = List(12, 2, 1, -10)

scala> QSort.qsort(l.toVector)(c)
res2: Vector[Int] = Vector(12, 2, 1, -10)

As you can see, whatever type I pass to qsort is the same type I get back.

Scala: make function polymorphic in data structure type

1 Answers