scala generic sort function doesn't work with arrays

Question

I'm trying to write a sorting function that would work with any sequence and returns the same sequence that is passed to this function. So I came up with this solution:

def qckSrt[U: Ordering, C <: Seq[U]](xs: C with SeqLike[U, C])
    (implicit bf: CanBuildFrom[C, U, C]): C = {
  val n = xs.length
  val b = bf()

  if (n <= 1) xs
  else {
    val p = xs.head
    val (left, right) = xs.tail partition { 
      implicitly[Ordering[U]].lteq(_, p)
    }
    b ++= qckSrt(left)
    b += p
    b ++= qckSrt(right)
    b.result()
  }
}

So it works with lists, vectors, arraybuffers... But it fails to work with ordinary array:

scala> qckSrt(Array(1, 2, 6, 2, 5))
<console>:16: error: inferred type arguments [Int,Any] do not conform to method qckSrt's type parameter bounds [U,C <: Seq[U]]
        qckSrt(Array(1, 2, 6, 2, 5))
        ^
<console>:16: error: type mismatch;
  found   : scala.collection.mutable.ArrayOps.ofInt
  required: C with scala.collection.SeqLike[U,C]
        qckSrt(Array(1, 2, 6, 2, 5))
               ^
<console>:16: error: No implicit Ordering defined for U.
        qckSrt(Array(1, 2, 6, 2, 5))

Is there a way to make this work for arrays also?

Why one would do that? SeqLike already has plenty of methods for sorting that just fine. — Michel Lemay
– Michel Lemay, Commented Aug 23, 2017 at 19:40

Oleg Pyzhcov · Accepted Answer · 2017-08-24 04:06:33Z

2

You can replace inheritance with an implicit conversion. For arrays, this will used implicit wrapping conversions, and for types that are already SeqLike, it will use a subtype evidence (implicitly[C[U] <:< SeqLike[U, C[U]]]):

import scala.collection._
import scala.collection.generic.CanBuildFrom


def qckSrt[U: Ordering, C[_]](xs: C[U])(implicit
  bf: CanBuildFrom[C[U], U, C[U]],
  asSeq: C[U] => SeqLike[U, C[U]]
): C[U] = {
  val n = xs.length
  val b = bf()

  if (n <= 1) xs
  else {
    val p = xs.head
    val (left, right) = xs.tail partition {
      implicitly[Ordering[U]].lteq(_, p)
    }
    b ++= qckSrt(left)
    b += p
    b ++= qckSrt(right)
    b.result()
  }
}

Adding a "hole" to a type C is required for U to be inferred properly at the call site.

answered Aug 24, 2017 at 4:06

Oleg Pyzhcov

7,3611 gold badge21 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

scala generic sort function doesn't work with arrays

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related