object IntList {

  trait List [T] {
    def isEmpty: Boolean
    def head: T
    def tail: List[T]
    def nth(n: Int): T
  }

  class Cons[T](val head: T, val tail: List[T]) extends List[T] {
    def isEmpty = false
    def nth(n: Int): T = {
      if (isEmpty) throw new IndexOutOfBoundsException
      if (n==0) head
      else tail nth(n - 1)
    }
  }

  class Nil[T] extends List[T] {
    def isEmpty: Boolean = true
    def head: Nothing = throw new NoSuchElementException("Nil.head")
    def tail: Nothing = throw new NoSuchElementException("Nil.tail")
    def nth(n: Int): Nothing = throw new NoSuchElementException("Nil.nth")
  }


  def run = {
    println("IntList")
    val list = new Cons(1, new Cons(2, new Cons(3, new Nil)))
    println(list nth 2)
    println(list nth 0)
    /* println(list nth 5) */
  }
}