S12

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向で。

view plainprint?

1. //P12 (**) Decode a run-length encoded list.  
2. //Given a run-length code list generated as specified in problem P10, construct its uncompressed version.  
3. //Example:  
4. //scala> decode(List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e)))  
5. //res0: List[Symbol] = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)  
6.   
7. def decode[T](xs: List[(Int, T)]) = {  
8.   
9.   // not tail recursion  
10.   def ntimes_nottail(n: Int, x: T): List[T] = {  
11.     if (n < 0) throw new IllegalArgumentException  
12.     else if (n == 0) Nil  
13.     else x :: ntimes_nottail(n - 1, x)  
14.   }  
15.   
16.   // tail recursion  
17.   def ntimes_tail(ntimes: Int, x: T) = {  
18.     def ntimes_rec(n: Int, result: List[T]): List[T] = {  
19.       if (n == 0) result else ntimes_rec(n - 1, x :: result)  
20.     }  
21.     if (ntimes < 0) throw new IllegalArgumentException else ntimes_rec(ntimes, Nil)  
22.   }  
23.   
24.   // tail recursion  
25.   def recursive(ys: List[(Int, T)], result: List[T]): List[T] = ys match {  
26.     case Nil => result  
27.     case (times, x) :: tail =>  recursive(tail, result ::: ntimes_tail(times, x))  
28. //    case (times, x) :: tail =>  recursive(tail, result ::: ntimes_nottail(times, x))  
29.   }  
30.   
31.   recursive(xs, Nil)  
32. }  
33.   
34.   
35. val l = List((5, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e))  
36. println(decode(l))  

//P12 (**) Decode a run-length encoded list.
//Given a run-length code list generated as specified in problem P10, construct its uncompressed version.
//Example:
//scala> decode(List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e)))
//res0: List[Symbol] = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)

def decode[T](xs: List[(Int, T)]) = {

  // not tail recursion
  def ntimes_nottail(n: Int, x: T): List[T] = {
    if (n < 0) throw new IllegalArgumentException
    else if (n == 0) Nil
    else x :: ntimes_nottail(n - 1, x)
  }

  // tail recursion
  def ntimes_tail(ntimes: Int, x: T) = {
    def ntimes_rec(n: Int, result: List[T]): List[T] = {
      if (n == 0) result else ntimes_rec(n - 1, x :: result)
    }
    if (ntimes < 0) throw new IllegalArgumentException else ntimes_rec(ntimes, Nil)
  }

  // tail recursion
  def recursive(ys: List[(Int, T)], result: List[T]): List[T] = ys match {
    case Nil => result
    case (times, x) :: tail =>  recursive(tail, result ::: ntimes_tail(times, x))
//    case (times, x) :: tail =>  recursive(tail, result ::: ntimes_nottail(times, x))
  }

  recursive(xs, Nil)
}


val l = List((5, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e))
println(decode(l))

末尾再帰版（ntimes_tail）だと100万回のループでもStackOverFlowにならなかったが、
非末尾再帰版だと10万回でStackOverFlowした。

解答例
そ、そんな！！