scala 通用排序函数不适用于数组

Question

我正在尝试编写一个排序函数，它可以处理任何序列并返回传递给该函数的相同序列。所以我想出了这个解决方案:

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

所以它适用于列表、向量、数组缓冲区......但它无法与普通数组一起使用:

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

有没有办法使这个工作也适用于数组？

Answer 1

您可以使用隐式转换替换继承。对于数组，这将使用隐式包装转换，对于已经是 SeqLike 的类型，它将使用子类型证据( 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()
  }
}

为类型添加“洞” C U 需要在调用站点正确推断。