Как написать «общую» сортировку слиянием в Scala?

Вот что у меня есть до сих пор:

  def mergesort[T <: Ordered[T]](elements : List[T]) : List[T] = {
    def merge(first : List[T], second : List[T]) : List[T] = (first, second) match {
      case (Nil, _) => second
      case (_, Nil) => first
      case (x :: xs, y :: ys) => if (x < y) x :: merge(xs, second) else y :: merge(first, ys)
    }

    if (elements.isEmpty) Nil
    else {
      val length = elements.length
      val (firstHalf, secondHalf) = elements.splitAt(length/2)

      merge(mergesort(firstHalf), mergesort(secondHalf))
    }
  }

Проблема, с которой я сталкиваюсь, заключается в том, что это терпит неудачу

mergesort(List(1, 3, 6, 3, 1, 0))

error: inferred type arguments [Int] do not conform to method mergesort's type parameter bounds [T <: Ordered[T]]
       mergesort(List(1, 3, 6, 3, 1, 0))
       ^

Есть ли способ заставить это работать для всех заказанных типов? Я думал, что Scala будет иметь какое-то неявное преобразование в «богатый» целочисленный тип, который, как я предполагал, будет иметь черту Ordered.


person Bwmat    schedule 24.03.2012    source источник
comment
См. несколько советов здесь: stackoverflow.com/questions/6929637/   -  person huynhjl    schedule 24.03.2012


Ответы (1)


Что вам нужно, так это представление, связанное def mergesort[T <% Ordered[T]]. См. ответы на этот вопрос: Универсальный метод для возврата первого из двух значений.

Теперь это будет соответствовать, но у вас есть некоторые ошибки в вашем алгоритме, которые приводят к ошибке переполнения стека в строке splitAt.

person Luigi Plinge    schedule 24.03.2012