Friday, November 5, 2010

S18

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

// P18 (**) Extract a slice from a list.
// Given two indices, I and K, the slice is the list containing the elements from and including the Ith element up to but not including the Kth element of the original list. Start counting the elements with 0.
// Example:
// scala> slice(3, 7, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
// res0: List[Symbol] = List('d, 'e, 'f, 'g)

def sliceBuiltin[T](i: Int, k: Int, xs: List[T]) = xs.slice(i, k)

def slice[T](i: Int, k: Int, xs: List[T]) = xs.drop(i).take(k - i)

def sliceZip[T](i: Int, k: Int, xs: List[T]) =
  xs.zipWithIndex.filter(x => i <= x._2).filter(x => x._2 < k).map(_._1)

def sliceFoldL[T](i: Int, k: Int, xs: List[T]) =
  xs.foldLeft((0, List[T]()))((acc, x) =>
    if(i <= acc._1 && acc._1 < k) (acc._1 + 1, x :: acc._2)
    else (acc._1 + 1, acc._2)
  )._2.reverse

def sliceRecursiveNotTail[T](i: Int, k: Int, xs: List[T]): List[T] = (i, k, xs) match {
  case (_, _, Nil)  => Nil
  case (0, _, h :: tail) if(0 < k) => h :: sliceRecursiveNotTail(0, k - 1, tail)
  case (_, _, _ :: tail) if(0 < i)  => sliceRecursiveNotTail(i - 1, k - 1, tail)
  case (_, 0, _) => Nil
}

def sliceRecursiveTail[T](i: Int, k: Int, xs: List[T]) = {
  def recursive(i: Int, k: Int, xs: List[T], acc: List[T]): List[T] =
    (i, k, xs) match {
      case (_, _, Nil)  => acc
      case (0, _, h :: tail) if(0 < k) => recursive(0, k - 1, tail, h :: acc)
      case (_, _, _ :: tail) if(0 < i)  => recursive(i - 1, k - 1, tail, acc)
      case (0, 0, _) => acc
    }
  recursive(i, k, xs, Nil).reverse
}

val l = (1 to 1000000) toList

//println(slice(1, 110000, l))
//println(sliceZip(1, 110000, l))
//println(sliceFoldL(1, 110000, l))
println(sliceRecursiveNotTail(1, 110000, l)) // StackOverFlow
//println(sliceRecursiveTail(1, 110000, l))


解答例
似たようなケースがある場合は、if文で書いた方がすっきりすることもあるのね。

No comments:

Post a Comment