2

我试图在 Scala 中实现合并排序。我得到以下内容：

def mergeSort[A: Ordering](as: List[A]): List[A] = as match {
  case Nil         => as
  case head :: Nil => as
  case _ => {
    val (l, r) = split(as)
    merge(mergeSort(l), mergeSort(r))
  }
}

def split[A](as: List[A]): (List[A], List[A]) = {
  def rec(todo: List[A], done: (List[A], List[A])): (List[A], List[A]) = todo match {
    case Nil          => done
    case head :: tail => rec(tail, (head :: done._2, done._1))
  }
  rec(as, (Nil, Nil))
}

def merge[A: Ordering](left: List[A], right: List[A]) = {
  def rec(left: List[A], right: List[A], done: List[A]): List[A] =
    (left, right) match {
      case (_, Nil) => rprepend(left, done)
      case (Nil, _) => rprepend(right, done)
      case (lh :: lt, rh :: rt) => if (implicitly[Ordering[A]].compare(lh, rh) <= 0)
        rec(lt, right, lh :: done)
        else rec(left, rt, rh :: done)
    }

  rec(left, right, Nil).reverse
}

def rprepend[A](prepend: List[A], as: List[A]): List[A] =
  prepend.foldLeft(as)((r, a) => a :: r)

这个问题不是关于正在进行的低效反转的淫秽数量，也不是关于缺乏尾递归的问题。相反，我注意到您可以通过传入如下排序算法来概括归并排序：

def generalizedMergeSort[A: Ordering](as: List[A], sort: List[A] => List[A]): List[A] = as match {
  case Nil         => as
  case head :: Nil => as
  case _ => {
    val (l, r) = split(as)
    merge(sort(l), sort(r))
  }
}

然后我尝试将mergesort重新实现为

def mergesort[A: Ordering](as: List[A]): List[A] = {
  generalizedMergeSort(as, mergesort)
}

但这无法编译，找不到正确的Ordering[A]：

[error] test.scala:17: No implicit Ordering defined for A.
[error]     generalizedMergeSort(as, mergesort)
[error]                              ^

作为将事情纳入范围的微弱尝试，我尝试过

def mergesort[A: Ordering](as: List[A]): List[A] = {
  implicit val realythere = implicitly[Ordering[A]]
  generalizedMergeSort(as, mergesort)
}

但无济于事。

我怀疑问题可能出在generalizedMergesort. 我说参数是 a List[A] => List[A]，但我传入 a ，List[A] => implicit Ordering[A] => List[A]但我不知道如何利用它来实现我的目标，即mergesort在generalizedMergesort和 本身方面实现。

4

2 回答 2

2

简单的解决方案是将隐式从方法提取到上层方法：

def mergesort[A: Ordering](as: List[A]): List[A] = {
  def mergesort0(xs: List[A]): List[A] = generalizedMergeSort(xs, mergesort0)
  mergesort0(as)
}

其次是用隐式包装你的函数（带有额外的对象创建）：

def mergesort[A: Ordering](as: List[A]): List[A] = {
  val mergesort0: List[A] => List[A] = xs => mergesort(xs)
  generalizedMergeSort(as, mergesort0)
}
于 2015-06-15T12:49:48.260 回答
2

您可以通过传递一个mergesort调用generalizedMergeSort. 此调用将捕获隐式Ordering：

def mergesort[A: Ordering](as: List[A]): List[A] = {
  generalizedMergeSort(as, mergesort(_: List[A]))
}

mergesort(_: List[A])是一个类型的闭包函数List[A] => List[A]，它mergesort使用它的参数调用，并且隐式Ordering参数在这个闭包中被捕获。

于 2015-06-15T12:51:56.937 回答