Неявное разрешение для аргумента функции

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

Затем я попытался повторно реализовать 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, Я говорю, что параметр является List[A] => List[A]но я прохожу в List[A] => implicit Ordering[A] => List[A] но я не знаю, как использовать это, чтобы добраться до моей цели реализации mergesort с точки зрения generalizedMergesort и себя.

Answer 1

Вы можете преодолеть это, передав функцию, которая вызывает 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 аргумент захватывается в этом закрытии.

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