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

次に、マージソートを次のように再実装しようとしました

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

しかし、役に立たない。

問題は の 2 番目のパラメーターにあると思われますgeneralizedMergesort。パラメータは a だと言いますが、 aList[A] => List[A]を渡しますが、それを利用してと 自体の観点からList[A] => implicit Ordering[A] => List[A]実装するという目標を達成する方法がわかりません。mergesortgeneralizedMergesort

4

2 に答える 2

2

を呼び出す関数を渡すことで、これを克服できmergesortますgeneralizedMergeSort。この呼び出しは暗黙の をキャプチャしますOrdering:

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

mergesort(_: List[A])は type のクロージャ関数であり、その引数List[A] => List[A]で呼び出さmergesortれ、暗黙のOrdering引数がこのクロージャに取り込まれます。

于 2015-06-15T12:51:56.937 に答える