CODEWITHSUNDEEP
scalarecursiontail-recursion
blue-sky
blue-sky

Reputation: 53786

How is this tail recursive method being iterated?

In below Scala method how is the List xs traversed by method nth? xs.tail is called recursively but why is the tail not always the same value since def tail in trait List just returns the list of parameterized types?

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

Upvotes: 2

Views: 320

Answers (2)

Keyel
Keyel

Reputation: 144

You have defined your List type recursively. This means, that you are using another lists for creating new ones. Naturally you have to make the first List somehow, that's why you have defined Nil.

So you can create an empty list without other lists:

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

and you can create not empty lists using already created lists, if you have an n-1 size List, you can create an n size one, saying, that the new list is the same as the old one (tail), plus the new elem (head):

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

If you inspect oneSize's tail, it turns out that it is the same object as empty

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

Let's define a list with 2 elems, using the oneSize list:

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

Inspecting the tail we get the oneSize list:

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

so using tail again we have to get the empty list again as before, and indeed:

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

Et voila, we've just iterated through the list, just as your nth function.

Upvotes: 3

0__
0__

Reputation: 67280

The List is a recursive structure. See the Wikipedia article on Cons. This is from that article:

enter image description here

The structure you would begin with is new Cons(42, new Cons(69, new Cons(613, new Nil))). Although the tail method also returns an instance of List[Int], that is not the same list, but the sub-list that follows one of the right-pointing arrows.

So if in your example, you would start with Cons(1, Cons(2, Cons(3, Nil))), let n be 2.

  • In the first iteration of function nth, we ask: Is Cons(1, Cons(2, Cons(3, Nil))) empty? No! Is n == 0? No. So recurse with the tail and n decremented.
  • In this second iteration, we ask: Is Cons(2, Cons(3, Nil)) empty (this is again a List[Int])? No. Is n == 0? No (it's 1 now). Go to the next recursion.
  • In the third iteration, we ask: Is Cons(3, Nil) empty? No. Is n == 0. Yes! Therefore, return the head of Cons(3, Nil) which is 3.

Upvotes: 7

Related Questions