count-chars.scala

/**
 * This function computes for each unique character in the list `chars` the number of
 * times it occurs. For example, the invocation
 *
 *   times(List('a', 'b', 'a'))
 *
 * should return the following (the order of the resulting list is not important):
 *
 *   List(('a', 2), ('b', 1))
 */
def times(chars: List[Char]): List[(Char, Int)] = {
  def increase(char: Char, count: List[(Char, Int)]): List[(Char, Int)] = count match {
    case Nil => List((char, 1))
    case (`char`, count) :: ys => (char, count + 1) :: ys
    case y :: ys => y :: increase(char, ys)
  }

  def iter(chars: List[Char], acc: List[(Char, Int)]): List[(Char, Int)] = chars match {
    case Nil => acc
    case y :: ys => iter(ys, increase(y, acc))
  }

  iter(chars, Nil)
}