函数参数的隐式解析

Question

我尝试在 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))
  }
}

然后我尝试重新实现合并排序

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的第二个参数上。我说参数是 List[A] => List[A]，但我传入了 List[A] => implicit Ordering[A] => List[A]，但我不知道如何利用它来实现我的目标 mergesort generalizedMergesort 和它自己。

Answer 1

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

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

Answer 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 参数在这个闭包中被捕获。

函数参数的隐式解析

implicit resolution for a function argument

scala

implicit

context-bound