S19

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

view plainprint?

1. // P19 (**) Rotate a list N places to the left.  
2. // Examples:  
3. // scala> rotate(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))  
4. // res0: List[Symbol] = List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'a, 'b, 'c)  
5. // scala> rotate(-2, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))  
6. // res1: List[Symbol] = List('j, 'k, 'a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i)  
7.   
8. def rotate[T](i: Int, xs: List[T]) = {  
9.   val splitted = xs.splitAt(i)  
10.   splitted._2 ::: splitted._1  
11. }  
12.   
13. // match - case version  
14. def rotateR[T](i: Int, xs: List[T]) = {  
15.   def r(i: Int, xs: List[T], acc: List[T]): List[T] = (i, xs) match {  
16.     case (_, h :: t) if 0 < i => r(i - 1, t, h :: acc) //tail recursion  
17.     case (0, rest) => rest ::: acc.reverse // Only 1 time.  
18.   }  
19.   if(i < 0 || xs.size <= i) xs else r(i, xs, Nil)  
20. }  
21.   
22. // if version  
23. def rotateRIf[T](i: Int, xs: List[T]) = {  
24.   def r(i: Int, xs: List[T], acc: List[T]): List[T] = {  
25.     if (0 < i) r(i -1, xs.tail, xs.head :: acc ) //tail recursion  
26.     else xs ::: acc.reverse // only 1 time.  
27.   }  
28.   if(i < 0 || xs.size <= i) xs else r(i, xs, Nil)  
29. }  
30.   
31. val l = (1 to 1000000) toList  
32.   
33. println(rotate(999999, l)) // ok  
34. println(rotateR(999999, l)) // ok  
35. println(rotateRIf(999999, l)) // ok  

// P19 (**) Rotate a list N places to the left.
// Examples:
// scala> rotate(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
// res0: List[Symbol] = List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'a, 'b, 'c)
// scala> rotate(-2, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
// res1: List[Symbol] = List('j, 'k, 'a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i)

def rotate[T](i: Int, xs: List[T]) = {
  val splitted = xs.splitAt(i)
  splitted._2 ::: splitted._1
}

// match - case version
def rotateR[T](i: Int, xs: List[T]) = {
  def r(i: Int, xs: List[T], acc: List[T]): List[T] = (i, xs) match {
    case (_, h :: t) if 0 < i => r(i - 1, t, h :: acc) //tail recursion
    case (0, rest) => rest ::: acc.reverse // Only 1 time.
  }
  if(i < 0 || xs.size <= i) xs else r(i, xs, Nil)
}

// if version
def rotateRIf[T](i: Int, xs: List[T]) = {
  def r(i: Int, xs: List[T], acc: List[T]): List[T] = {
    if (0 < i) r(i -1, xs.tail, xs.head :: acc ) //tail recursion
    else xs ::: acc.reverse // only 1 time.
  }
  if(i < 0 || xs.size <= i) xs else r(i, xs, Nil)
}

val l = (1 to 1000000) toList

println(rotate(999999, l)) // ok
println(rotateR(999999, l)) // ok
println(rotateRIf(999999, l)) // ok

解答例
へそ曲がりめ！