Skip to content

Instantly share code, notes, and snippets.

@ryanoneill
Created April 3, 2012 19:48
Show Gist options
  • Save ryanoneill/2295094 to your computer and use it in GitHub Desktop.
Save ryanoneill/2295094 to your computer and use it in GitHub Desktop.
Ninety-Nine Scala Problems: Problem 08 - Eliminate consecutive duplicates of list elements.
// http://aperiodic.net/phil/scala/s-99/
// P08 (**) Eliminate consecutive duplicates of list elements.
// If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed.
// Example:
// scala> compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
// res0: List[Symbol] = List('a, 'b, 'c, 'a, 'd, 'e)
object Problem08 {
def main(args: Array[String]) {
val values = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
println(compress(values))
}
// def compress[T](values: List[T]) : List[T] =
// values match {
// case Nil => Nil
// case x :: y :: xs if (x == y) => compress(y :: xs)
// case x :: xs => List(x) ::: compress(xs)
// }
def compress[T](values: List[T]) : List[T] =
compressTail(Nil, values)
def compressTail[T](seen: List[T], remaining: List[T]) : List[T] =
remaining match {
case Nil => seen
case x :: y :: xs if (x == y) => compressTail(seen, y :: xs)
case x :: xs => compressTail(seen ::: List(x), xs)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment