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

Question

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

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

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

Answer 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, точно так же, как и там, где останавливается серия рекурсивных вызовов.

Answer 2

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

Answer 3

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

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. В настоящее время, кажется, нет способа скрыть это. Это может или не может беспокоить вас.

Answer 4

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

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

Не обращайте внимания на синтетические вещи, важно то, что _rlRec является меткой (даже если она выглядит как функция), а «вызов» _rlRec во второй ветви сопоставления с образцом будет скомпилирован как переход в байт-коде.

Answer 5

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

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

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

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