Showing posts with label s-99. Show all posts
Showing posts with label s-99. Show all posts

Saturday, November 13, 2010

S25

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

// P25 (*) Generate a random permutation of the elements of a list.
// Hint: Use the solution of problem P23.
// Example:
// scala> randomPermute(List('a, 'b, 'c, 'd, 'e, 'f))
// res0: List[Symbol] = List('b, 'a, 'd, 'c, 'e, 'f)

// P20 (*) Remove the Kth element from a list.
def removeAt[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)
}

import scala.util.Random
def randomPermute[T](xs: List[T]) = {
  val rand = new Random
  def r(ys: List[T], acc: List[T]): List[T] = {
    if(ys.size == 1) ys.head :: acc
    else {
      val (rest, removed) = removeAt(rand.nextInt(ys.size), ys)
      r(rest, removed :: acc)
    }
  }
  if(xs.isEmpty) Nil else r(xs, Nil)
}
解答例
またもや、してやられたぜ!

S24

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

// P24 (*) Lotto: Draw N different random numbers from the set 1..M.
// Example:
// scala> lotto(6, 49)
// res0: List[Int] = List(23, 1, 17, 33, 21, 37)

import scala.util.Random
def lotto(n: Int, to: Int) = {
  val rand = new Random()
  def r(acc: List[Int]): List[Int] = {
    def next(): Int = {
      val i = rand.nextInt(to)
      if(acc.count(_ == i) == 0) i else next
    }
    if(acc.size < n) r(next :: acc) else acc
  }
  if(n < 1 || to < n) throw new IllegalArgumentException
  else r(Nil)
}
解答例
こりゃ一本とられたわい

S23

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

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

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

Friday, November 12, 2010

S22

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

// P22 (*) Create a list containing all integers within a given range.
//  Example:
// scala> range(4, 9)
// res0: List[Int] = List(4, 5, 6, 7, 8, 9)

def rangeTail(from: Int, to: Int) = {
  def r(current: Int, acc: List[Int]): List[Int] = {
    if(current <= to) r(current + 1, current :: acc)
    else acc.reverse
  }
  r(from, Nil)
}

def rangeBuiltin(from: Int, to: Int) = List.range(from, to + 1).toList

解答例
unfoldRightっていう発想はなかった。 だけど、末尾再帰じゃないじゃないか。 これじゃすぐstackoverflowだ。 ということで、unfoldRightの末尾再帰版を書いてみた。
def unfoldRightTail[A, B](s: B)(f: B => Option[(A, B)]): List[A] = {
  def recursive(s: B, acc: List[A]): List[A] = {
    f(s) match {
      case None         => acc.reverse
      case Some((r, n)) => recursive(n, r :: acc)
    }
  }
  recursive(s, Nil)
}
def rangeFunctionalTail(start: Int, end: Int): List[Int] =
  unfoldRightTail(start) { n =>
    if (n > end) None
    else Some((n, n + 1))
  }

Wednesday, November 10, 2010

S21

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

// P21 (*) Insert an element at a given position into a list.
// Example:
// scala> insertAt('new, 1, List('a, 'b, 'c, 'd))
// res0: List[Symbol] = List('a, 'new, 'b, 'c, 'd)

def insertAt[T](e :T, n: Int, xs: List[T]) = {
  def r(n: Int, rest: List[T], acc: List[T]): List[T] = (n, rest) match {
    case (0, h :: t) => acc.reverse ::: List(e) ::: rest
    case (_, h :: t) => r(n - 1, t, h :: acc)
  }
  if(n < 0 || xs.size <= n) throw new NoSuchElementException else r(n, xs, Nil)
}

def insertAt2[T](e :T, n: Int, xs: List[T]) = {
  if(n < 0 || xs.size <= n) throw new NoSuchElementException
  val splitted = xs.splitAt(n)
  splitted._1 ::: List(e) :::  splitted._2
}
解答例
君、それ好きだよね。

Tuesday, November 9, 2010

S20

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

// P20 (*) Remove the Kth element from a list.
// Return the list and the removed element in a Tuple. Elements are numbered from 0.
// Example:
// scala> removeAt(1, List('a, 'b, 'c, 'd))
// res0: (List[Symbol], Symbol) = (List('a, 'c, 'd),'b)

def removeAt[T](i: Int, xs: List[T]) =
  if(i < 0 || xs.size <= i) throw new NoSuchElementException
  else (xs.zipWithIndex.filter{_._2 != i}.map{_._1}, xs(i))

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

解答例の上のやつ、いいね。

Saturday, November 6, 2010

S19

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

// P19 (**) Rotate a list N places to the left.
// Examples:
// scala> rotate(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
// res0: List[Symbol] = List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'a, 'b, 'c)
// scala> rotate(-2, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
// res1: List[Symbol] = List('j, 'k, 'a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i)

def rotate[T](i: Int, xs: List[T]) = {
  val splitted = xs.splitAt(i)
  splitted._2 ::: splitted._1
}

// match - case version
def rotateR[T](i: Int, xs: List[T]) = {
  def r(i: Int, xs: List[T], acc: List[T]): List[T] = (i, xs) match {
    case (_, h :: t) if 0 < i => r(i - 1, t, h :: acc) //tail recursion
    case (0, rest) => rest ::: acc.reverse // Only 1 time.
  }
  if(i < 0 || xs.size <= i) xs else r(i, xs, Nil)
}

// if version
def rotateRIf[T](i: Int, xs: List[T]) = {
  def r(i: Int, xs: List[T], acc: List[T]): List[T] = {
    if (0 < i) r(i -1, xs.tail, xs.head :: acc ) //tail recursion
    else xs ::: acc.reverse // only 1 time.
  }
  if(i < 0 || xs.size <= i) xs else r(i, xs, Nil)
}

val l = (1 to 1000000) toList

println(rotate(999999, l)) // ok
println(rotateR(999999, l)) // ok
println(rotateRIf(999999, l)) // ok

解答例
へそ曲がりめ!

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文で書いた方がすっきりすることもあるのね。

Thursday, November 4, 2010

S17

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

// P17 (*) Split a list into two parts.
// The length of the first part is given. Use a Tuple for your result.
// Example:
// scala> split(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
// res0: (List[Symbol], List[Symbol]) = (List('a, 'b, 'c),List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k))

// tail revursion but too slow
def split_tail_too_slow[T](nth: Int, xs: List[T]) = {
  def recursive(n: Int, rest: List[T], acc: (List[T], List[T])): (List[T], List[T]) = rest match {
    case Nil => throw new NoSuchElementException
    case l if (n == 0) => (acc._1, l)
    case h :: t => recursive(n - 1, t, (acc._1 ::: List(h), Nil)) // add to tail -> O(n)
  }
  if(nth <= 0) throw new IllegalArgumentException else recursive(nth, xs, (Nil, Nil))
}

// tail revursion
def split_tail_fast[T](nth: Int, xs: List[T]) = {
  def recursive(n: Int, rest: List[T], acc: (List[T], List[T])): (List[T], List[T]) = rest match {
    case Nil => throw new NoSuchElementException
    case l if (n == 0) => (acc._1.reverse, l)
    case h :: t => recursive(n - 1, t, (List(h) ::: acc._1 , Nil)) // add to head -> O(1)

  }
  if(nth <= 0) throw new IllegalArgumentException else recursive(nth, xs, (Nil, Nil))
}

def split_take[T](nth: Int, xs: List[T]): (List[T], List[T]) =
  (xs.take(nth) , xs.takeRight(xs.length - nth))

val l = (1 to 1000000).toList
println(split_take(100000, l))
println(split_tail_fast(100000, l))
println(split_tail_too_slow(100000, l)) // 超遅い

3方式で書いてみた。

split_tail_too_slowはリストの最後尾に追加する。追加の度にリストをたどらなければならないので、再帰の度に遅くなる。O(n)
split_tail_fastはリストの先頭に追加するため、リストの要素数に関係なくO(1)
split_tail_takeはList APIを使ったバージョン。


100万個のリストで(10万, 90万)で分割(split_take以外の2つは10万回再帰)してみたところ、
split_tail_too_slowはいつまでたっても終わらなかった。

末尾再帰にすりゃいいってもんじゃないのね。勉強になりました。

解答例
ふむふむ、splitAtってのがあるのね。
match式にタプルを使えばいいのか。if式がいらなくなるのね。なるほど。

S16

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

// P16 (**) Drop every Nth element from a list.
// Example:
// scala> drop(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
// res0: List[Symbol] = List('a, 'b, 'd, 'e, 'g, 'h, 'j, 'k)

// not tail recursive version
def drop_nottail[T](n: Int, xs: List[T]): List[T] = xs match {
  case h :: t if (n == 1) => drop_nottail(n - 1, t)
  case h :: t => h :: drop_nottail(n - 1, t)
  case Nil => xs
}

// tail recursive version
def drop_tail[T](nth: Int, xs: List[T]) = {
  def recursive[T](n: Int, tail: List[T], acc: List[T]): List[T] = tail match {
    case h :: t if (n == 1) => recursive(n - 1, t, acc)
    case h :: t => recursive(n - 1, t, h :: acc)
    case Nil => acc
  }
  recursive(nth, xs, Nil).reverse
}

// zipwithindex version
def drop_zipWithIndex[T](nth: Int, xs: List[T]) = {
  xs.zipWithIndex.flatMap{
    case (_, i) if (i + 1 == nth) => Nil // drop nth
    case (e, _) => e :: Nil
  }
}

val l: List[Int] = (1 to 100000).toList
//println(drop_nottail(3, l)) // StackOverflowError
//println(drop_tail(3, l))
println(drop_zipWithIndex(3, l))


解答例
そうまでして1行で書きたいってか!!

S15

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向だけど、List要素の増殖は以前書いたので今回はList.fillを使った。

// P15 (**) Duplicate the elements of a list a given number of times.
//     Example:
//     scala> duplicateN(3, List('a, 'b, 'c, 'c, 'd))
//     res0: List[Symbol] = List('a, 'a, 'a, 'b, 'b, 'b, 'c, 'c, 'c, 'c, 'c, 'c, 'd, 'd, 'd)

def duplicateN[T](n: Int, xs: List[T]): List[T] = xs match {
  case Nil => xs
  case h :: t => List.fill(n)(h) ::: duplicateN(n, t)
}

def duplicateN_tail[T](n: Int, xs: List[T]) = {
  def recursive[T](n: Int, tail: List[T], acc: List[T]): List[T] = tail match {
    case Nil => acc
    case h :: t => recursive(n, t, List.fill(n)(h) ::: acc)
  }
  recursive(n, xs, Nil).reverse
}

def duplicateN_map[T](n: Int, xs: List[T]) = xs.flatMap(List.fill(n)(_))

val l = List('a, 'b, 'c, 'c, 'd)
println(duplicateN_tail(100000, l))
println(duplicateN_map(100000, l))
println(duplicateN(100000, l))  // 末尾再帰じゃないはずだが、stackoverflowにならないのが不思議


解答例
やっぱりそうきますか。

Wednesday, November 3, 2010

S14

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

// P14 (*) Duplicate the elements of a list.
// Example:
// scala> duplicate(List('a, 'b, 'c, 'c, 'd))
// res0: List[Symbol] = List('a, 'a, 'b, 'b, 'c, 'c, 'c, 'c, 'd, 'd)

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

def duplicate_tail[T](xs: List[T]) = {
  def recursive(ys: List[T], acc: List[T]): List[T] = ys match {
    case Nil => acc
    case h :: t => recursive(t, h :: h :: acc)
  }
  recursive(xs, Nil).reverse
}

def duplicate_map[T](xs: List[T]): List[T] = xs.flatMap{ x => x :: x :: Nil}

//val l = List('a, 'b, 'c, 'c, 'd)
val l = 1 to 1000000 toList

println(duplicate_tail(l))
println(duplicate_map(l))
println(duplicate(l)) // StackOverFlow

解答例
そうですよね。

Tuesday, November 2, 2010

S12

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

//P12 (**) Decode a run-length encoded list.
//Given a run-length code list generated as specified in problem P10, construct its uncompressed version.
//Example:
//scala> decode(List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e)))
//res0: List[Symbol] = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)

def decode[T](xs: List[(Int, T)]) = {

  // not tail recursion
  def ntimes_nottail(n: Int, x: T): List[T] = {
    if (n < 0) throw new IllegalArgumentException
    else if (n == 0) Nil
    else x :: ntimes_nottail(n - 1, x)
  }

  // tail recursion
  def ntimes_tail(ntimes: Int, x: T) = {
    def ntimes_rec(n: Int, result: List[T]): List[T] = {
      if (n == 0) result else ntimes_rec(n - 1, x :: result)
    }
    if (ntimes < 0) throw new IllegalArgumentException else ntimes_rec(ntimes, Nil)
  }

  // tail recursion
  def recursive(ys: List[(Int, T)], result: List[T]): List[T] = ys match {
    case Nil => result
    case (times, x) :: tail =>  recursive(tail, result ::: ntimes_tail(times, x))
//    case (times, x) :: tail =>  recursive(tail, result ::: ntimes_nottail(times, x))
  }

  recursive(xs, Nil)
}


val l = List((5, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e))
println(decode(l))


末尾再帰版(ntimes_tail)だと100万回のループでもStackOverFlowにならなかったが、
非末尾再帰版だと10万回でStackOverFlowした。

解答例
そ、そんな!!

Monday, November 1, 2010

S10, S11

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

// P10 (*) Run-length encoding of a list.
// Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as tuples (N, E) where N is the number of duplicates of the element E.
// Example:
// scala> encode(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
// res0: List[(Int, Symbol)] = List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e))

def pack[A](ls: List[A]): List[List[A]] = {
  if (ls.isEmpty) List(List())
  else {
    val (packed, next) = ls span { _ == ls.head }
    if (next == Nil) List(packed)
    else{
      packed :: pack(next)
    }
  }
}
def encode[T](xs: List[T]) = {
  pack(xs).map{ (x) => (x.length, x.head) }
}

def encodeModified[T](xs: List[T]) = {
  pack(xs).map{ (x) => if(x.length == 1) x.head else (x.length, x.head) }
}


解答例
同じだ。

S09

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

// P09 (**) Pack consecutive duplicates of list elements into sublists.
// If a list contains repeated elements they should be placed in separate sublists.
// Example:
// scala> pack(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
// res0: List[List[Symbol]] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))

// tail recursion
def reverse[T](xs: List[T]): List[T] = {
  def recursive[T](ys: List[T], result: List[T]): List[T] = ys match {
    case Nil => result
    case h :: t => recursive(t, h :: result)
  }
  recursive(xs, Nil)
}

// tail recursion
def removeLast[T](xs: List[T]): List[T] = {
  def recursive[T](ys: List[T], result: List[T]): List[T] = ys match {
    case Nil => throw new NoSuchElementException
    case h :: Nil => result
    case h :: t => recursive(t, h :: result)
  }
  reverse(recursive(xs, Nil))
}

// tail recursion
def pack[T](xs: List[T]): List[List[T]] = {
  def recursive(rest: List[T], acc: List[List[T]]): List[List[T]] = {
    rest match {
      case Nil => acc
      case h :: t if(acc != Nil && h == acc.last.head) => 
        val nextAcc = List(h :: acc.last) //List[Listt[T]]
        recursive(t, removeLast(acc) ++ nextAcc) // List[List[T]] ++ List[List[T]] => List[List[T]]
      case h :: t =>
        val nextAcc = acc ++ List(List(h))
        recursive(t, nextAcc)
    }
  }
  recursive(xs, Nil)
}

val l = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
println(pack(l)) //=>  List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))


解答例
spanっすか。

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
  }

Saturday, October 30, 2010

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


解答例

Thursday, October 28, 2010

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してる。