S15

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向だけど、List要素の増殖は以前書いたので今回はList.fillを使った。

view plainprint?

1. // P15 (**) Duplicate the elements of a list a given number of times.  
2. //     Example:  
3. //     scala> duplicateN(3, List('a, 'b, 'c, 'c, 'd))  
4. //     res0: List[Symbol] = List('a, 'a, 'a, 'b, 'b, 'b, 'c, 'c, 'c, 'c, 'c, 'c, 'd, 'd, 'd)  
5.   
6. def duplicateN[T](n: Int, xs: List[T]): List[T] = xs match {  
7.   case Nil => xs  
8.   case h :: t => List.fill(n)(h) ::: duplicateN(n, t)  
9. }  
10.   
11. def duplicateN_tail[T](n: Int, xs: List[T]) = {  
12.   def recursive[T](n: Int, tail: List[T], acc: List[T]): List[T] = tail match {  
13.     case Nil => acc  
14.     case h :: t => recursive(n, t, List.fill(n)(h) ::: acc)  
15.   }  
16.   recursive(n, xs, Nil).reverse  
17. }  
18.   
19. def duplicateN_map[T](n: Int, xs: List[T]) = xs.flatMap(List.fill(n)(_))  
20.   
21. val l = List('a, 'b, 'c, 'c, 'd)  
22. println(duplicateN_tail(100000, l))  
23. println(duplicateN_map(100000, l))  
24. println(duplicateN(100000, l))  // 末尾再帰じゃないはずだが、stackoverflowにならないのが不思議  

// 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にならないのが不思議

解答例
やっぱりそうきますか。