• List is immutable, its elements can’t be changed
• List is recursive

• All the elements of list have the same type
• All lists are constructed from
  • An empty list Nil
  • Operator cons (::)
• Operators ending with “:” is calculated from right to left

A :: B :: C is interpreted A :: (B :: C)

Functions on list

• Implement of last

def last[T](xs: List[T]): T = xs match {
  case List() => throw new Error("Empty list")
  case List(x) => x
  case y :: ys => last(ys)
}

• Implement of init

def init[T](xs: List[T]): List[T] = xs match {
  case List() => throw new Error("init of empty list")
  case List(_) => List()
  case y :: ys => y :: init(ys)
}

• Implement of concat

def concat[T](xs: List[T], ys: List[T]): List[T] = xs match {
  case List() => ys
  case z :: zs => z :: concat(zs, ys)
}

• Implement of reverse

def reverse[T](xs: List[T]): List[T] = xs match {
  case List() => List()
  case y :: ys => reverse(ys) ::: List(y)
}

• Implement of removeAt

def removeAt[T](xs: List[T], n: Int): List[T] = {
  if(n < 0 || n > xs.length - 1) throw new Error("Can't remove")
  var count = n
  xs match {
    case y :: ys => if(count == 0) ys else {
      count = count - 1
      y :: removeAt(ys, count)
    }
  }
}

List patterns

• Nil: an empty list
• p :: ps: this pattern will match any lists whose head matches p and tail matches ps
• List(p1, …, pn) is the same as p1 :: … :: pn :: Nil