Scala: filtering operation. Didactic

filter_using.scala

// Filtering elements in a list (here they're kept if positive)
def posElems(xs: List[Int]): List[Int] = xs match {
  case Nil     => xs
  case y :: ys => if (y > 0) y :: posElems(ys) else posElems(ys)
}

// A simple way to define filter
// In reality it's more complicated because:
// * It works for arbitrary collections, not only lists
// * Its tail recursive
abstract class List[T] {
  ...
  def filter(p: T => Boolean): List[T] = this match {
    case Nil     =>
    case x :: xs => if (p(x)) xx :: xs.filter(p) else xs.filter(p)
  }
}

// Back to posElems
def posElems(xs: List[Int]): List[Int] = xs filter (x => x > 0)

// Now real world examples of filtering
xs filter p
xs filterNot p // Elements that do not satisfy predicate p
xs partition p // A par containing those who satisfy p and those who dont
xs takeWhile p // Longest prefix of xs that satisfy p
xs dropWhile p // Remainder of xs after leading elements that satisfy p removed
xs span p // (xs takeWhile p, xs dropWhile p) but faster

val nums = List(2, -4, 5, 7, 1)
nums filter (x => x > 0) // List(2, 5, 7, 1)
nums filterNot (x => x > 0) // List(-4)
nums partition (x => x > 0) // (List(2, 5, 7, 1), List(-4))
nums takeWhile (x => x > 0) // List(2)
nums dropWhile (x => x > 0) // List(-4, 5, 7, 1)
nums span (x => x > 0) // (List(2), List(-4, 5, 7, 1))

// EXAMPLE1: Pack consecutive duplicates into sublists
// pack(List("a", "a", "a", "b", "c", "c", "a")) should give
// List(List("a", "a", "a"), List("b"), List("c", "c"), List("a"))
def pack[T](xs: List[T]): List[List[T]] = xs match {
  case Nil      => Nil
  case x :: xs1 =>
    val (first, rest) = xs span (y => x == y)
    first :: pack(rest) 
}

// EXAMPLE2: Encode the run-length encoding of a list
// encode(List("a", "a", "a", "b", "c", "c", "a")) should give
// List(("a", 3), ("b", 1), ("c", 2), ("a", 1))
def encode[T](xs: List[T]): List[(T, Int)] = {
  pack(xs) map (ys => (ys.head, ys.length)) // We use pack, and map!
}