Created
April 3, 2012 21:02
-
-
Save ryanoneill/2295489 to your computer and use it in GitHub Desktop.
Ninety-Nine Scala Problems: Problem 10 - Run-length encoding of a list.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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