scala - 这个尾部递归方法是如何迭代的？

在下面的Scala方法中，如何通过方法xs遍历列表nth？递归调用xs.tail，但是为什么尾部并不总是相同的值，因为特征def tail中的List仅返回参数化类型的列表？

object nth {

  def nth[T](n: Int, xs: List[T]): T =
    if (xs.isEmpty) throw new IndexOutOfBoundsException
    else if (n == 0) xs.head
    else {
        nth(n - 1, xs.tail)
        }                                 //> nth: [T](n: Int, xs: week4.List[T])T
  val list = new Cons(1, new Cons(2, new Cons(3, new Nil)))
  nth(2 , list)   > res0: Int=3
}

trait List[T] {
  def isEmpty: Boolean
  def head: T
  def tail: List[T]
}
class Cons[T](val head: T, val tail: List[T]) extends List[T]{
  def isEmpty = false
}
class Nil[T] extends List[T]{
  def isEmpty = true
  def head : Nothing = throw new NoSuchElementException("Nil.head")
  def tail : Nothing = throw new NoSuchElementException("Nil.tail")
}

最佳答案

List是一个递归结构。参见Wikipedia article on Cons。这是从该文章:

您将开始使用的结构是new Cons(42, new Cons(69, new Cons(613, new Nil)))。尽管tail方法也返回List[Int]的实例，该实例不是相同的列表，但是跟随右指向箭头之一的子列表。

因此，如果在您的示例中以Cons(1, Cons(2, Cons(3, Nil)))开头，则让n为2。

在nth函数的的第一个迭代中，我们问:Cons(1, Cons(2, Cons(3, Nil)))是否为空？没有!是n == 0吗？不。所以递减，尾部和n递减。

在此的第二次迭代中，我们问:Cons(2, Cons(3, Nil))是否为空(这又是List[Int])？不，是n == 0吗？否(现在是1)。转到下一个递归。

在第三次迭代中，我们问:Cons(3, Nil)是否为空？不，是n == 0。是!因此，返回Cons(3, Nil)的开头，即3。

关于scala - 这个尾部递归方法是如何迭代的？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14219867/

cons

scala - 这个尾部递归方法是如何迭代的？