Skip to content

Instantly share code, notes, and snippets.

@ryanoneill
Created April 3, 2012 21:02
Show Gist options
  • Save ryanoneill/2295489 to your computer and use it in GitHub Desktop.
Save ryanoneill/2295489 to your computer and use it in GitHub Desktop.
Ninety-Nine Scala Problems: Problem 10 - Run-length encoding of a list.
// http://aperiodic.net/phil/scala/s-99/
// P10 (*) Run-length encoding of a list.
// Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as tuples (N, E) where N is the number of duplicates of the element E.
// Example:
// scala> encode(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
// res0: List[(Int, Symbol)] = List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e))
import Problem09.pack
object Problem10 {
def main(args : Array[String]) {
val values = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
println(encode(values))
}
def head[T](values : List[T]) : T =
values match {
case x :: xs => x
case _ => throw new NoSuchElementException
}
// Kept getting a type mismatch problem
// when trying to switch map to be tail recursive
def map[A, B](values : List[A])(f: A => B) : List[B] =
values match {
case Nil => Nil
case x :: xs => f(x) :: map(xs) { f }
}
// length has already been defined
// in a previous problem so it's ok to use the builtin
def encode[T](values : List[T]) : List[(Int, T)] =
map(pack(values)) { x => (x length, head(x)) }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment