Drop elements

We are chugging along nicely. Let's look at element removal:

Here comes the method definition:

scala> :paste 
// Entering paste mode (ctrl-D to finish) 
 
  def drop[A](l: List[A], n: Int): List[A] = 
    if (n <= 0) l 
    else l match { 
      case Nil => Nil 
      case _ :: t => drop(t, n - 1) 
    } 

We drop n (or less than n) elements starting at the beginning of the list. If there are less than n elements, we return a Nil (empty) list.

What is the complexity of the drop method? It is O(n), as we might end up traversing the entire list.

The dropWhile method takes a list and predicate function. It invokes the function on successive elements and drops them if it evaluates to true. It stops when the function evaluates to false:

scala> def dropWhile[A](l: List[A], f: A => Boolean): List[A] = l match { 
     |     case x :: xs if f(x) => dropWhile(xs, f) 
     |     case _ => l 
     |   } 
...