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
  }

S07

P06はしょうもないので省略。

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

// P07 (**) Flatten a nested list structure.
// Example:
// scala> flatten(List(List(1, 1), 2, List(3, List(5, 8))))
// res0: List[Any] = List(1, 1, 2, 3, 5, 8)

def flatten(xs: List[Any]): List[Any] = {
  def recursive(rest: List[Any], result: List[Any]): List[Any] = rest match {
    case Nil => result
    case head :: tail => 
      head match {
        case Nil => recursive(tail, result)
        case h :: t => recursive(tail, recursive(t, recursive(List(h), result)))
        case notaList => recursive(tail, result ::: List(notaList))
      } 
    case notaList => result ::: List(notaList)
  }
  recursive(xs, Nil)
}

解答例
ちくしょー！反則だ（笑

S05

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

// P05 (*) Reverse a list.
// Example:
// scala> reverse(List(1, 1, 2, 3, 5, 8))
// res0: List[Int] = List(8, 5, 3, 2, 1, 1)

def builtIn[T](xs: List[T]): List[T] = xs.reverse

def recursive[T](xs: List[T]): List[T] = xs match {
  case Nil => xs
  case h :: tail => recursive(tail) ::: List(h)
}

// 末尾再帰版
def tailRecursive[T](xs: List[T]): List[T] = {
  def recursive[T](rest: List[T], result: List[T] ): List[T] = rest match {
    case Nil => result
    case h :: tail => recursive(tail, List(h) ::: result)
  }
  recursive(xs, Nil)
}

解答例
foldLeftってのがあったか！

def foldLeft[T](xs: List[T]): List[T] = 
  xs.foldLeft(List[T]()){(r, h) => h :: r}

S04

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

//P04 (*) Find the number of elements of a list.
//Example:
//scala> length(List(1, 1, 2, 3, 5, 8))
//res0: Int = 6

def lengthBuiltIn[T](xs: List[T]): Int = xs.length

// 末尾再帰版
def lengthTailRecursive[T](xs: List[T]): Int = {
  def recursive(l: List[T], n: Int): Int = l match {
    case Nil => 0
    case _ :: Nil => n + 1
    case _ :: tail => recursive(tail, n + 1)
  }
  recursive(xs, 0)
}

def length[T](xs: List[T]): Int = {
  def recursive(l: List[T]): Int = l match {
    case Nil => 0
    case _ :: tail => 1 + recursive(tail)
  }
  recursive(xs)
}

解答例

S03

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

// P03 (*) Find the Kth element of a list.
// By convention, the first element in the list is element 0.
//
// Example:
// scala> nth(2, List(1, 1, 2, 3, 5, 8))
// res0: Int = 2

def nth[T](n: Int, xs: List[T]): T = xs match {
  case Nil => throw new NoSuchElementException
  case _ if(n < 0 || xs.length <= n) => throw new IllegalArgumentException
  case h :: _ if(n == 0)=> h
  case _ :: tail => nth(n - 1, tail)
}

解答例はタプルにしてmatch-caseしてる。

S02

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

P02 (*) Find the last but one element of a list.
Example:
scala> penultimate(List(1, 1, 2, 3, 5, 8))
res0: Int = 5

def penultimate[T](xs: List[T]): T = xs match  {
  case x :: _ :: Nil => x
  case _ :: tail => penultimate(tail)
  case _ => throw new Exception("no such element")
}

def lastNthBuiltln[A](n: Int, ls: List[A]) = {
  if(n <= 0) throw new IllegalArgumentException
  if(ls.size < n) throw new NoSuchElementException
  ls.takeRight(n).head
}

def lastNth[A](n: Int, ls: List[A]): A = {
  if(n <= 0) throw new IllegalArgumentException
  if(ls.size < n) throw new NoSuchElementException
  ls match {
    case xs if(ls.length == n) => xs.head
    case _ :: tail => lastNth(n, tail)
    case Nil => throw new NoSuchElementException
  }
}

S01

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

とりあえず、P01を試してみた。
P01 (*) Find the last element of a list.
Example:
scala> last(List(1, 1, 2, 3, 5, 8))
res0: Int = 8

def last[T](xs: List[T]): T = xs match {
    case h :: Nil => h
    case _ :: tail => last(tail) 
    case _ => throw new NoSuchElementException
  }