Sunday, October 31, 2010

S08

S-99: Ninety-Nine Scala Problemsを試してみる。

// P08 (**) Eliminate consecutive duplicates of list elements.
// If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed.
// Example:
// scala> compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
// res0: List[Symbol] = List('a, 'b, 'c, 'a, 'd, 'e)

def compress[T](xs: List[T]): List[T] = {
  // simple reverse (not tail recursion..)
  def reverse[T](ys: List[T]): List[T] = ys match {
    case Nil => ys
    case head :: tail => reverse(tail) ::: List(head)
  }
  def recursive[T](rest: List[T], result: List[T]): List[T] = rest match{
    case Nil => result
    case head :: tail if(result.isEmpty || head != result.head) =>
        recursive(tail, List(head) ::: result)
    case _ :: tail => recursive(tail, result)
  }
  reverse(recursive(xs, Nil))
}


解答例

またおまえか、foldRight!!
そりゃ、試すさ。

// FoldLeft
def compressFoldL[T](xs: List[T]): List[T] = 
  xs.foldLeft(List[T]()){ (acc, x) =>  
    if(acc.isEmpty || acc.last != x) acc ::: List(x)
    else acc
  }

// /: (FoldLeft)
def compressFoldL2[T](xs: List[T]): List[T] = 
  (List[T]() /: xs){ (acc, x) =>  
    if(acc.isEmpty || acc.last != x) acc ::: List(x)
    else acc
  }

// FoldRight
def compressFildR[A](xs: List[A]): List[A] =
  xs.foldRight(List[A]()) { (x, acc) =>
    if (acc.isEmpty || acc.head != x) x :: acc
    else acc
  }

// :\ (FoldRight)
def compressFildR2[A](xs: List[A]): List[A] =
  (xs :\ List[A]()) { (x, acc) =>
    if (acc.isEmpty || acc.head != x) x :: acc
    else acc
  }

No comments:

Post a Comment