2

在下面的 Scala 方法中，List 是如何被xs方法遍历的nth？xs.tail被递归调用，但为什么尾部并不总是相同的值，因为def tail在 trait 中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")
}
4

2 回答 2

7

是List递归结构。请参阅关于 Cons 的 Wikipedia 文章。这是来自那篇文章：

在此处输入图像描述

您要开始的结构是new Cons(42, new Cons(69, new Cons(613, new Nil))). 尽管该tail方法还返回 的实例List[Int]，但它不是同一个列表，而是指向右箭头之一的子列表。

因此，如果在您的示例中，您将从Cons(1, Cons(2, Cons(3, Nil))), let nbe开始2。

  • 在函数的第一次迭代中nth，我们问：是Cons(1, Cons(2, Cons(3, Nil)))空的吗？不！是n == 0吗？不，所以用尾巴递归并n递减。
  • 在第二次迭代中，我们问：是Cons(2, Cons(3, Nil))空的（这又是 a List[Int]）？不，是n == 0吗？不（1现在是）。进入下一个递归。
  • 在第三次迭代中，我们问：是Cons(3, Nil)空的吗？不，是n == 0。是的！因此，返回其头部Cons(3, Nil)为3。
于 2013-01-08T17:18:59.783 回答
3

您已经递归地定义了 List 类型。这意味着，您正在使用另一个列表来创建新列表。自然你必须以某种方式创建第一个 List，这就是你定义 Nil 的原因。

因此，您可以创建一个没有其他列表的空列表：

val empty = new Nil[Int]                  //> empty  : Nil[Int] = Nil@1f93f8

并且您可以使用已创建的列表创建非空列表，如果您有一个 n-1 大小的列表，您可以创建一个 n 大小的列表，即新列表与旧列表（尾部）相同，加上新列表元素（头部）：

val oneSize = new Cons(1, empty)          //> oneSize  : Cons[Int] = Cons@b159eb

如果你检查 oneSize 的尾巴，结果证明它是同一个对象empty

oneSize.tail                              //> res0: List[Int] = Nil@1f93f8

让我们使用 oneSize 列表定义一个包含 2 个元素的列表：

val twoSize = new Cons(2, oneSize)        //> twoSize  : Cons[Int] = Cons@18654ae

检查尾部，我们得到 oneSize 列表：

twoSize.tail                              //> res1: List[Int] = Cons@b159eb

所以再次使用 tail 我们必须像以前一样再次获取空列表，实际上：

twoSize.tail.tail                         //> res2: List[Int] = Nil@1f93f8

等等，我们刚刚迭代了列表，就像你的第 n 个函数一样。

于 2013-01-08T18:36:51.410 回答