反向列表Scala

发布时间：2020-12-16 09:21:22 所属栏目：安全来源：网络整理

导读：给出以下代码： import scala.util.Randomobject 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

给出以下代码：

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

为什么第一个版本的功能失败(对于大输入),而第二个变体工作.我怀疑这是与尾递归相关的东西,但我不太确定.有人可以给我“虚拟人”的解释吗？

解决方法

好吧,让我尝试一下假人的尾递归递归

如果你遵循反向列表需要做的,你会得到

reverseList(List(1,2,3,4))
reverseList(List(2,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,1)

用rlRec,你有

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

不同之处在于,在第一种情况下,重写会越来越长.你必须记住在最后一次递归调用reverseList之后要完成的事情：要添加到结果中的元素.堆栈是用来记住的.当这太远时,你会发生堆栈溢出.相反,使用rlRec,重写的大小一直相同.当最后一个rlRec完成时,结果可用.没有什么可做的,没有什么可记住的,不需要堆栈.关键是在rlRec中,递归调用是返回rlRec(其他),而在reverseList中它是返回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启动创建的循环将退出,就像递归调用系列停止的那样.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!