S08

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

view plainprint?

1. // P08 (**) Eliminate consecutive duplicates of list elements.  
2. // 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.  
3. // Example:  
4. // scala> compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))  
5. // res0: List[Symbol] = List('a, 'b, 'c, 'a, 'd, 'e)  
6.   
7. def compress[T](xs: List[T]): List[T] = {  
8.   // simple reverse (not tail recursion..)  
9.   def reverse[T](ys: List[T]): List[T] = ys match {  
10.     case Nil => ys  
11.     case head :: tail => reverse(tail) ::: List(head)  
12.   }  
13.   def recursive[T](rest: List[T], result: List[T]): List[T] = rest match{  
14.     case Nil => result  
15.     case head :: tail if(result.isEmpty || head != result.head) =>  
16.         recursive(tail, List(head) ::: result)  
17.     case _ :: tail => recursive(tail, result)  
18.   }  
19.   reverse(recursive(xs, Nil))  
20. }  

// 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!!
そりゃ、試すさ。

view plainprint?

1. // FoldLeft  
2. def compressFoldL[T](xs: List[T]): List[T] =   
3.   xs.foldLeft(List[T]()){ (acc, x) =>    
4.     if(acc.isEmpty || acc.last != x) acc ::: List(x)  
5.     else acc  
6.   }  
7.   
8. // /: (FoldLeft)  
9. def compressFoldL2[T](xs: List[T]): List[T] =   
10.   (List[T]() /: xs){ (acc, x) =>    
11.     if(acc.isEmpty || acc.last != x) acc ::: List(x)  
12.     else acc  
13.   }  
14.   
15. // FoldRight  
16. def compressFildR[A](xs: List[A]): List[A] =  
17.   xs.foldRight(List[A]()) { (x, acc) =>  
18.     if (acc.isEmpty || acc.head != x) x :: acc  
19.     else acc  
20.   }  
21.   
22. // :\ (FoldRight)  
23. def compressFildR2[A](xs: List[A]): List[A] =  
24.   (xs :\ List[A]()) { (x, acc) =>  
25.     if (acc.isEmpty || acc.head != x) x :: acc  
26.     else acc  
27.   }  

// 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
を試してみる。

view plainprint?

1. // P07 (**) Flatten a nested list structure.  
2. // Example:  
3. // scala> flatten(List(List(1, 1), 2, List(3, List(5, 8))))  
4. // res0: List[Any] = List(1, 1, 2, 3, 5, 8)  
5.   
6. def flatten(xs: List[Any]): List[Any] = {  
7.   def recursive(rest: List[Any], result: List[Any]): List[Any] = rest match {  
8.     case Nil => result  
9.     case head :: tail =>   
10.       head match {  
11.         case Nil => recursive(tail, result)  
12.         case h :: t => recursive(tail, recursive(t, recursive(List(h), result)))  
13.         case notaList => recursive(tail, result ::: List(notaList))  
14.       }   
15.     case notaList => result ::: List(notaList)  
16.   }  
17.   recursive(xs, Nil)  
18. }  

// 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)

view plainprint?

1. def builtIn[T](xs: List[T]): List[T] = xs.reverse  
2.   
3. def recursive[T](xs: List[T]): List[T] = xs match {  
4.   case Nil => xs  
5.   case h :: tail => recursive(tail) ::: List(h)  
6. }  
7.   
8. // 末尾再帰版  
9. def tailRecursive[T](xs: List[T]): List[T] = {  
10.   def recursive[T](rest: List[T], result: List[T] ): List[T] = rest match {  
11.     case Nil => result  
12.     case h :: tail => recursive(tail, List(h) ::: result)  
13.   }  
14.   recursive(xs, Nil)  
15. }  

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ってのがあったか！

view plainprint?

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

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

S04

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

view plainprint?

1. //P04 (*) Find the number of elements of a list.  
2. //Example:  
3. //scala> length(List(1, 1, 2, 3, 5, 8))  
4. //res0: Int = 6  
5.   
6. def lengthBuiltIn[T](xs: List[T]): Int = xs.length  
7.   
8. // 末尾再帰版  
9. def lengthTailRecursive[T](xs: List[T]): Int = {  
10.   def recursive(l: List[T], n: Int): Int = l match {  
11.     case Nil => 0  
12.     case _ :: Nil => n + 1  
13.     case _ :: tail => recursive(tail, n + 1)  
14.   }  
15.   recursive(xs, 0)  
16. }  
17.   
18. def length[T](xs: List[T]): Int = {  
19.   def recursive(l: List[T]): Int = l match {  
20.     case Nil => 0  
21.     case _ :: tail => 1 + recursive(tail)  
22.   }  
23.   recursive(xs)  
24. }  

//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

view plainprint?

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

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

view plainprint?

1. def penultimate[T](xs: List[T]): T = xs match  {  
2.   case x :: _ :: Nil => x  
3.   case _ :: tail => penultimate(tail)  
4.   case _ => throw new Exception("no such element")  
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")
}

view plainprint?

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

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
}

view plainprint?

1. def lastNth[A](n: Int, ls: List[A]): A = {  
2.   if(n <= 0) throw new IllegalArgumentException  
3.   if(ls.size < n) throw new NoSuchElementException  
4.   ls match {  
5.     case xs if(ls.length == n) => xs.head  
6.     case _ :: tail => lastNth(n, tail)  
7.     case Nil => throw new NoSuchElementException  
8.   }  
9. }  

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

view plainprint?

1. def last[T](xs: List[T]): T = xs match {  
2.     case h :: Nil => h  
3.     case _ :: tail => last(tail)   
4.     case _ => throw new NoSuchElementException  
5.   }  

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