S23

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

view plainprint?

1. // P23 (**) Extract a given number of randomly selected elements from a list.  
2. // Example:  
3. // scala> randomSelect(3, List('a, 'b, 'c, 'd, 'f, 'g, 'h))  
4. // res0: List[Symbol] = List('e, 'd, 'a)  
5.   
6. import scala.util.Random  
7.   
8. // P20 (*) Remove the Kth element from a list.  
9. def removeAtR[T](i: Int, xs: List[T]) = {  
10.   def r(i: Int, xs: List[T], acc: List[T]): (List[T], T) = (i, xs) match {  
11.     case (0, h :: t) => (acc.reverse ::: t, h)  
12.     case (i, h :: t) => r(i - 1, t, h :: acc)  
13.   }  
14.   if(i < 0 || xs.size <= i) throw new NoSuchElementException else r(i, xs, Nil)  
15. }  
16.   
17. def randomSelect[T](n: Int, xs: List[T]) = {  
18.   val rand = new Random()  
19.   def r(ys: List[T], acc: List[T]): List[T] = {  
20.     val (rest, removed) = removeAtR(rand.nextInt(ys.size), ys)  
21.     if(n <= acc.size + 1) removed :: acc  
22.     else r(rest, removed :: acc)  
23.   }  
24.   if(n <= 0 || xs.size < n) throw new IllegalArgumentException  
25.   else r(xs, Nil)  
26. }  

// P23 (**) Extract a given number of randomly selected elements from a list.
// Example:
// scala> randomSelect(3, List('a, 'b, 'c, 'd, 'f, 'g, 'h))
// res0: List[Symbol] = List('e, 'd, 'a)

import scala.util.Random

// P20 (*) Remove the Kth element from a list.
def removeAtR[T](i: Int, xs: List[T]) = {
  def r(i: Int, xs: List[T], acc: List[T]): (List[T], T) = (i, xs) match {
    case (0, h :: t) => (acc.reverse ::: t, h)
    case (i, h :: t) => r(i - 1, t, h :: acc)
  }
  if(i < 0 || xs.size <= i) throw new NoSuchElementException else r(i, xs, Nil)
}

def randomSelect[T](n: Int, xs: List[T]) = {
  val rand = new Random()
  def r(ys: List[T], acc: List[T]): List[T] = {
    val (rest, removed) = removeAtR(rand.nextInt(ys.size), ys)
    if(n <= acc.size + 1) removed :: acc
    else r(rest, removed :: acc)
  }
  if(n <= 0 || xs.size < n) throw new IllegalArgumentException
  else r(xs, Nil)
}

解答例
君のは違うけど、わしのは末尾再帰だよ。