Обратный список Scala

С учетом следующего кода:

import scala.util.Random

object Reverser {

  // Fails for big list
  def reverseList[A](list : List[A]) : List[A] = {
    list match {
      case Nil => list
      case (x :: xs) => reverseList(xs) ::: List(x)
    }
  }

  // Works
  def reverseList2[A](list : List[A]) : List[A] = {
    def rlRec[A](result : List[A], list : List[A]) : List[A] = {
      list match {
        case Nil => result
        case (x :: xs) => { rlRec(x :: result, xs) }
      }
    }
    rlRec(Nil, list)
  }

  def main(args : Array[String]) : Unit = {
    val random = new Random
    val testList = (for (_ <- 1 to 2000000) yield (random.nextInt)).toList
    // val testListRev = reverseList(testList) <--- Fails
    val testListRev = reverseList2(testList)
    println(testList.head)
    println(testListRev.last)
  }
}

Почему первая версия функции не работает (для больших входов), а второй вариант работает. Я подозреваю, что это связано с хвостовой рекурсией, но я не очень уверен. Может кто-нибудь, пожалуйста, дайте мне объяснение "для чайников"?

Ответы

Ответ 1

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

Если вы выполните то, что нужно сделать с помощью reverseList, вы получите

reverseList(List(1,2,3, 4))
reverseList(List(2,3,4):::List(1)
(reverseList(List(3,4):::List(2)):::List(1)   
((reverseList(List(4):::List(3)):::List(2)):::List(1)
Nil:::List(4):::List(3):::List(2):::List(1)
List(4,3,2,1)

С rlRec у вас есть

rlRec(List(1,2,3,4), Nil)
rlRec(List(2,3,4), List(1))
rlREc(List(3,4), List(2,1))
rlRec(List(4), List(3,2,1))
rlRec(Nil, List(4,3,2,1))
List(4,3,2,1)

Разница в том, что в первом случае переписывание продолжает увеличиваться. Вы должны помнить, что нужно делать после того, как завершится последний рекурсивный вызов reverseList: элементы, добавляемые к результату. Стек используется для запоминания этого. Когда это заходит слишком далеко, вы получаете переполнение стека. Наоборот, с rlRec переписывание имеет одинаковый размер. Когда последний rlRec завершается, результат доступен. Больше нечего делать, ничего не помнить, нет необходимости в стеке. Ключ в том, что в rlRec рекурсивный вызов return rlRec(something else), а в reverseList - return f(reverseList(somethingElse)), с f beging _ ::: List(x). Вы должны помнить, что вам нужно будет вызвать f (что подразумевает также запоминание x) (возврат не требуется в scala, просто добавленный для ясности. Также обратите внимание, что val a = recursiveCall(x); doSomethingElse() совпадает с doSomethingElseWith(recursiveCall(x)), поэтому это не хвостовой вызов)

Когда у вас есть рекурсивный хвостовой вызов

def f(x1,...., xn)
    ...
    return f(y1, ...yn)
    ...

на самом деле нет необходимости запоминать контекст первого f, когда второй возвращается. Поэтому его можно переписать

def f(x1....xn)
start:
    ...
    x1 = y1, .... xn = yn
    goto start
    ...

Это то, что делает компилятор, поэтому вы избегаете.

Конечно, функция f должна иметь где-то возвращение, которая не является рекурсивным вызовом. Вот где цикл, созданный с помощью goto start, выйдет, так же, как это происходит, когда останавливается серия рекурсивных вызовов.

Ответ 2

Функция называется tail recursive, когда она вызывает себя как последнее действие. Вы можете проверить, есть ли функция tail recursive, добавив аннотацию @tailrec.

Ответ 3

Как отмечали другие, устранение хвостового вызова позволяет избежать роста стека, когда он не нужен. Если вам интересно, что делает оптимизация, вы можете запустить

scalac -Xprint:tailcalls MyFile.scala

... показать промежуточное представление компилятора после фазы исключения. (Обратите внимание, что вы можете сделать это после любой фазы, и вы можете распечатать список фаз с помощью scala -Xshow-phase.)

Например, для вашей внутренней, рекурсивной функции rlRec она дает мне:

def rlRec[A >: Nothing <: Any](result: List[A], list: List[A]): List[A] = {
  <synthetic> val _$this: $line2.$read.$iw.$iw.type = $iw.this;
  _rlRec(_$this,result,list){
    list match {
      case immutable.this.Nil => result
      case (hd: A, tl: List[A])collection.immutable.::[A]((x @ _), (xs @ _)) => _rlRec($iw.this, {
        <synthetic> val x$1: A = x;
        result.::[A](x$1)
      }, xs)
    }
  }
}

Nevermind там синтетический материал, важно то, что _rlRec - это метка (даже если она похожа на функцию), а "вызов" на _rlRec во второй ветки сопоставления шаблонов собирается скомпилироваться как скачок в байт-коде.

Ответ 4

Вы можете сделать свою хвостовую рекурсивную версию такой же простой, как и не-хвостовая рекурсивная версия, используя аргумент по умолчанию, чтобы дать начальное значение для результатов:

def reverseList[A](list : List[A], result: List[A] = Nil) : List[A] = list match {
  case Nil => result
  case (x :: xs) => reverseList(xs, x :: result)
}

Хотя вы можете использовать это так же, как и другие, т.е. reverseList(List(1,2,3,4)), к сожалению, вы раскрываете деталь реализации с необязательным параметром result. В настоящее время, похоже, нет способа скрыть это. Это может вас беспокоить или не беспокоить.

Ответ 5

Первый метод не является хвостовым рекурсивным. См:

case (x :: xs) => reverseList(xs) ::: List(x)

Последняя вызванная операция - это :::, а не рекурсивный вызов reverseList. Другой - хвостовой рекурсивный.

Ответ 6

def reverse(n: List[Int]): List[Int] = {
  var a = n
  var b: List[Int] = List()
  while (a.length != 0) {
    b = a.head :: b
    a = a.tail
  }
  b
}

Когда вы вызываете вызов функции так,

reverse(List(1,2,3,4,5,6))

тогда он даст ответ так:

res0: List[Int] = List(6, 5, 4, 3, 2, 1)