Как повторяется этот хвостовой рекурсивный метод?

В приведенном ниже методе 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")
}

recursion scala tail-recursion
person blue-sky    schedule 08.01.2013    source источник
comment
вы переопределяете голову и хвост в Cons значениями и, следовательно, результатом. определение в признаке является абстрактным.   -  person aishwarya    schedule 08.01.2013
comment
@aishwarya хвост возвращает список из [T], как повторяются элементы списка?   -  person blue-sky    schedule 08.01.2013
comment
список здесь не является списком в истинном смысле. Минусы - это экземпляр List, и это то, что возвращается;)   -  person aishwarya    schedule 08.01.2013
comment
как указал @aishwarya, методы isEmpty, head, tail, определенные в List[T] trait, являются абстрактными и определяют только тип возвращаемого значения. Таким образом, метод tail должен возвращать реализацию List[T]. Cons реализует его, определяя val tail в параметрах своего конструктора, и это то, что возвращается при вызове tail для экземпляра Cons.   -  person pagoda_5b    schedule 08.01.2013

Ответы (2)


arrow_upward
7
arrow_downward

List является рекурсивной структурой. См. статью Википедии о минусах. Это из той статьи:

введите здесь описание изображения

Структура, с которой вы начали бы, это 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.
person 0__    schedule 08.01.2013
comment
Хотя метод tail также возвращает экземпляр List[Int], это не тот же самый список, а подсписок, следующий за одной из стрелок, указывающих вправо. Хорошо, но как получить подсписок? Есть ли какая-то неявная функциональность, перемещающая указатель вперед? - person blue-sky; 08.01.2013
comment
Ничего неявного. Звонок xs.tail в nth(n - 1, xs.tail). Это движение указателя, вы переходите от xs к xs.tail. Для непустого списка, который является ячейкой Cons, возвращается подсписок (val tail). Для пустого списка (Nil) возникнет исключение. - person 0__; 08.01.2013
comment
Я не понимал, что метод «хвост» - это то, что перемещает указатель, поскольку каждый раз, когда он вызывается, он делит список на новую голову и хвост. Спасибо - person blue-sky; 09.01.2013

arrow_upward
3
arrow_downward

Вы определили свой тип списка рекурсивно. Это означает, что вы используете другие списки для создания новых. Естественно, вам нужно как-то составить первый список, поэтому вы определили 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:

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

Осматривая хвост, мы получаем список oneSize:

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

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

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

И вуаля, мы только что прошлись по списку, как и ваша n-я функция.

person Keyel    schedule 08.01.2013