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

Question

我正在尝试编写一个适用于任何序列的排序函数，returns 传递给此函数的相同序列。所以我想出了这个解决方案：

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

需要将 "hole" 添加到类型 C 才能在调用站点正确推断 U。

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

scala generic sort function doesn't work with arrays

scala

scala-collections