Thursday, November 4, 2010


S-99: Ninety-Nine Scala Problemsを試してみる。

// P15 (**) Duplicate the elements of a list a given number of times.
//     Example:
//     scala> duplicateN(3, List('a, 'b, 'c, 'c, 'd))
//     res0: List[Symbol] = List('a, 'a, 'a, 'b, 'b, 'b, 'c, 'c, 'c, 'c, 'c, 'c, 'd, 'd, 'd)

def duplicateN[T](n: Int, xs: List[T]): List[T] = xs match {
  case Nil => xs
  case h :: t => List.fill(n)(h) ::: duplicateN(n, t)

def duplicateN_tail[T](n: Int, xs: List[T]) = {
  def recursive[T](n: Int, tail: List[T], acc: List[T]): List[T] = tail match {
    case Nil => acc
    case h :: t => recursive(n, t, List.fill(n)(h) ::: acc)
  recursive(n, xs, Nil).reverse

def duplicateN_map[T](n: Int, xs: List[T]) = xs.flatMap(List.fill(n)(_))

val l = List('a, 'b, 'c, 'c, 'd)
println(duplicateN_tail(100000, l))
println(duplicateN_map(100000, l))
println(duplicateN(100000, l))  // 末尾再帰じゃないはずだが、stackoverflowにならないのが不思議


No comments:

Post a Comment