Объединить сортировку с "Программирование Scala" вызывает переполнение стека

Ответ 1

Он делает это, потому что он не является хвостовым рекурсивным. Вы можете исправить это либо с помощью нестрогой коллекции, либо путем ее хвостовой рекурсии.

Последнее решение выглядит следующим образом:

def msort[T](less: (T, T) => Boolean) 
            (xs: List[T]): List[T] = { 
  def merge(xs: List[T], ys: List[T], acc: List[T]): List[T] = 
    (xs, ys) match { 
      case (Nil, _) => ys.reverse ::: acc 
      case (_, Nil) => xs.reverse ::: acc
      case (x :: xs1, y :: ys1) => 
        if (less(x, y)) merge(xs1, ys, x :: acc) 
        else merge(xs, ys1, y :: acc) 
    } 
  val n = xs.length / 2 
  if (n == 0) xs 
  else { 
    val (ys, zs) = xs splitAt n 
    merge(msort(less)(ys), msort(less)(zs), Nil).reverse
  } 
} 

Использование нестрогости включает либо передачу параметров по имени, либо использование нестрогих коллекций, таких как Stream. Следующий код использует Stream только для предотвращения и List в другом месте:

def msort[T](less: (T, T) => Boolean) 
            (xs: List[T]): List[T] = { 
  def merge(left: List[T], right: List[T]): Stream[T] = (left, right) match {
    case (x :: xs, y :: ys) if less(x, y) => Stream.cons(x, merge(xs, right))
    case (x :: xs, y :: ys) => Stream.cons(y, merge(left, ys))
    case _ => if (left.isEmpty) right.toStream else left.toStream
  }
  val n = xs.length / 2 
  if (n == 0) xs 
  else { 
    val (ys, zs) = xs splitAt n 
    merge(msort(less)(ys), msort(less)(zs)).toList
  } 
}

Ответ 2

Просто играя с scala TailCalls (поддержка батутов), о которой я подозреваю, не было, когда этот вопрос был первоначально задан. Здесь рекурсивная неизменная версия слияния в Rex answer.

import scala.util.control.TailCalls._

def merge[T <% Ordered[T]](x:List[T],y:List[T]):List[T] = {

  def build(s:List[T],a:List[T],b:List[T]):TailRec[List[T]] = {
    if (a.isEmpty) {
      done(b.reverse ::: s)
    } else if (b.isEmpty) {
      done(a.reverse ::: s)
    } else if (a.head<b.head) {
      tailcall(build(a.head::s,a.tail,b))
    } else {
      tailcall(build(b.head::s,a,b.tail))
    }
  }

  build(List(),x,y).result.reverse
}

Работает так же быстро, как измененная версия на большом List[Long] на scala 2.9.1 на 64-битном OpenJDK (Debian/Squeeze amd64 на i7).

Ответ 3

На всякий случай решения Daniel не дали достаточно ясного представления, проблема заключается в том, что рекурсия слияния столь же глубока, как длина списка, и это не хвостовая рекурсия, поэтому она не может быть преобразована в итерацию.

Scala может преобразовать решение хвостового рекурсивного решения Daniel в нечто приблизительно эквивалентное этому:

def merge(xs: List[T], ys: List[T]): List[T] = {
  var acc:List[T] = Nil
  var decx = xs
  var decy = ys
  while (!decx.isEmpty || !decy.isEmpty) {
    (decx, decy) match { 
      case (Nil, _) => { acc = decy.reverse ::: acc ; decy = Nil }
      case (_, Nil) => { acc = decx.reverse ::: acc ; decx = Nil }
      case (x :: xs1, y :: ys1) => 
        if (less(x, y)) { acc = x :: acc ; decx = xs1 }
        else { acc = y :: acc ; decy = ys1 }
    }
  }
  acc.reverse
}

но он отслеживает все переменные для вас.

(Хвост-рекурсивный метод - это метод, в котором метод только вызывает себя, чтобы получить полный ответ для возврата, он никогда не вызывает себя, а затем делает что-то с результатом перед его передачей. Кроме того, хвостовая рекурсия не может если этот метод может быть полиморфным, поэтому он обычно работает только в объектах или классах, отмеченных как final.)