S09

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

view plainprint?

1. // P09 (**) Pack consecutive duplicates of list elements into sublists.  
2. // If a list contains repeated elements they should be placed in separate sublists.  
3. // Example:  
4. // scala> pack(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))  
5. // res0: List[List[Symbol]] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))  
6.   
7. // tail recursion  
8. def reverse[T](xs: List[T]): List[T] = {  
9.   def recursive[T](ys: List[T], result: List[T]): List[T] = ys match {  
10.     case Nil => result  
11.     case h :: t => recursive(t, h :: result)  
12.   }  
13.   recursive(xs, Nil)  
14. }  
15.   
16. // tail recursion  
17. def removeLast[T](xs: List[T]): List[T] = {  
18.   def recursive[T](ys: List[T], result: List[T]): List[T] = ys match {  
19.     case Nil => throw new NoSuchElementException  
20.     case h :: Nil => result  
21.     case h :: t => recursive(t, h :: result)  
22.   }  
23.   reverse(recursive(xs, Nil))  
24. }  
25.   
26. // tail recursion  
27. def pack[T](xs: List[T]): List[List[T]] = {  
28.   def recursive(rest: List[T], acc: List[List[T]]): List[List[T]] = {  
29.     rest match {  
30.       case Nil => acc  
31.       case h :: t if(acc != Nil && h == acc.last.head) =>   
32.         val nextAcc = List(h :: acc.last) //List[Listt[T]]  
33.         recursive(t, removeLast(acc) ++ nextAcc) // List[List[T]] ++ List[List[T]] => List[List[T]]  
34.       case h :: t =>  
35.         val nextAcc = acc ++ List(List(h))  
36.         recursive(t, nextAcc)  
37.     }  
38.   }  
39.   recursive(xs, Nil)  
40. }  
41.   
42. val l = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)  
43. println(pack(l)) //=>  List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))  

// P09 (**) Pack consecutive duplicates of list elements into sublists.
// If a list contains repeated elements they should be placed in separate sublists.
// Example:
// scala> pack(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
// res0: List[List[Symbol]] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))

// tail recursion
def reverse[T](xs: List[T]): List[T] = {
  def recursive[T](ys: List[T], result: List[T]): List[T] = ys match {
    case Nil => result
    case h :: t => recursive(t, h :: result)
  }
  recursive(xs, Nil)
}

// tail recursion
def removeLast[T](xs: List[T]): List[T] = {
  def recursive[T](ys: List[T], result: List[T]): List[T] = ys match {
    case Nil => throw new NoSuchElementException
    case h :: Nil => result
    case h :: t => recursive(t, h :: result)
  }
  reverse(recursive(xs, Nil))
}

// tail recursion
def pack[T](xs: List[T]): List[List[T]] = {
  def recursive(rest: List[T], acc: List[List[T]]): List[List[T]] = {
    rest match {
      case Nil => acc
      case h :: t if(acc != Nil && h == acc.last.head) => 
        val nextAcc = List(h :: acc.last) //List[Listt[T]]
        recursive(t, removeLast(acc) ++ nextAcc) // List[List[T]] ++ List[List[T]] => List[List[T]]
      case h :: t =>
        val nextAcc = acc ++ List(List(h))
        recursive(t, nextAcc)
    }
  }
  recursive(xs, Nil)
}

val l = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
println(pack(l)) //=>  List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))

解答例
spanっすか。