implicit resolution for a function argument

Question

I tried to implement mergesort in Scala. I got to the following:

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)

This question is not about the obscene amount of inefficient reversing going on, nor about the lack of tail recursion. Rather, I noticed that you could generalize mergesort by passing in a sort algorithm like so:

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

Then I tried re-implementing mergesort as

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

but this fails to compile, not finding the proper Ordering[A]:

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

as a feeble attempt to get things in scope I tried

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

but to no avail.

I suspect the problem may be in the second parameter of generalizedMergesort. I say the parameter is a List[A] => List[A], but I pass in a List[A] => implicit Ordering[A] => List[A] but I don't know how to make use of that to get to my goal of implementing mergesort in terms of generalizedMergesort and itself.

Answer 1

You can overcome this by passing a function that calls mergesort to generalizedMergeSort. This call will capture the implicit Ordering:

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

mergesort(_: List[A]) is a closure function of type List[A] => List[A], which calls mergesort with its argument, and the implicit Ordering argument gets captured in this closure.

Answer 2

The simple solution is to extract implicit from method to upper method:

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

and second is to wrap your function with implicit (with additional object creation):

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