[ネタ] Scala 99 でリバビリ中

Main.scala

// scala99 http://aperiodic.net/phil/scala/s-99/

object Scala99 {
  import Function.{const, uncurried}
  
//P01 (*) Find the last element of a list.
//    Example:
//
//    scala> last(List(1, 1, 2, 3, 5, 8))
//    res0: Int = 8
  def last[A](x: List[A]): A =
    x.reduceRight[A](uncurried(const(identity)))

//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[A](x: List[A]): A =
    x.foldRight[(() => A, Int)]((() => throw new NoSuchElementException, 0)){ 
      (x, t) => (if (t._2 == 1) () => x else t._1, t._2 + 1)}._1()

//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[A](n: Int, x: List[A]): A =
    x.foldRight[Int => A](_ => throw new NoSuchElementException) {
       (x, kxs) => {case 0 => x; case n => kxs(n - 1)}}(n) 
        
//P04 (*) Find the number of elements of a list.
//    Example:
//
//    scala> length(List(1, 1, 2, 3, 5, 8))
//    res0: Int = 6
  def length[A](x: List[A]): Int = 
    x.foldRight[Int](0){(_, sum) => sum + 1}
       
//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 reverse[A](x: List[A]): List[A] =
    x.foldRight[List[A] => List[A]](identity)((x, kxs) => xs => kxs(x :: xs))(Nil)
    
//    x.foldRight[List[A]](Nil)((x, xs) => xs :+ x) // ok, but performance is bad: O(N^2)

//P06 (*) Find out whether a list is a palindrome.
//    Example:
//
//    scala> isPalindrome(List(1, 2, 3, 2, 1))
//    res0: Boolean = true
  def isPalindrome[A](x: List[A]) =
    x.foldRight[(Boolean, List[A])](true -> x){(rx, acc) => acc match {
      case (b, x :: xs) => (b && (rx == x), xs)}}._1

//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(x: List[_]) = {
    def flattenV(x: List[_], v: List[_]): List[_] =
      x.foldRight[List[_]](Nil){(any, tail) => any match {
        case l: List[_] => flattenV(l, tail)
        case x => x :: tail
      }
    }
    flattenV(x, Nil)
  }
  
//
//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[A](x: List[A]) = 
    x.foldRight[List[A]](Nil) { (a, bs) => bs match {
    case b :: _ if a == b => bs
    case _ => a :: bs
    }}

//
//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))
  def pack[A](x: List[A]) =
    x.foldRight[List[List[A]]](Nil) { (a, acc) => acc match {
      case (b :: bs) :: bss if a == b => (a :: b :: bs) :: bss
      case _ => List(a) :: acc
    }}
  
//
//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 encode[A](x: List[A]) =
    x.foldRight[List[(Int, A)]](Nil) { (a, acc) => acc match {
      case (n, b) :: ts if a == b => (n + 1, b) :: ts
      case _ => (1, a) :: acc
    }}
  
//
//P11 (*) Modified run-length encoding.
//    Modify the result of problem P10 in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as (N, E) terms.
//
//    Example:
//
//    scala> encodeModified(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
//    res0: List[Any] = List((4,'a), 'b, (2,'c), (2,'a), 'd, (4,'e))
  def encodeModified[A](x: List[A]) =
    x.foldRight[List[_]](Nil) { (a, acc) => acc match {
      case b :: ts if a == b => (2, b) :: ts
      case (n: Int, b) :: ts if a == b => (n + 1, b) :: ts
      case _ => a :: acc
    }}
  
//
//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[A](x: List[(Int, A)]) =
    x.foldRight(List[A]()) { (t, acc) =>
      List.fill(t._1)(t._2) ++ acc
    }
  
//
//P13 (**) Run-length encoding of a list (direct solution).
//    Implement the so-called run-length encoding data compression method directly. I.e. don't use other methods you've written (like P09's pack); do all the work directly.
//
//    Example:
//
//    scala> encodeDirect(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))
  
// omitted: my solution to P10 is direct  
  
//
//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[A](x: List[A]) = 
    x.foldRight(List[A]()){(e, acc) => e :: e :: acc}
  
//
//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[A](n: Int, x: List[A]) = 
    x.foldRight(List[A]()){(e, acc) => List.fill(n)(e) ++ acc}
  
//
//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)
  def drop[A](c: Int, x: List[A]) =
    x.foldRight[(Int, (List[A] => List[A])) => (List[A] => List[A])]((_, x) => x) {
      (x, kcnt) => (n, klst) => kcnt(n + 1, (xs: List[A]) => klst(if (n % c == 0) xs else x :: xs))
  }(1, identity)(Nil)
  
  def dropUsingFoldRightTwice[A](c: Int, x: List[A]) =
    x.foldRight[(Int, List[A]) => List[A]]((_, x) => x) {
      (x, kcnt) => (n, xs) => kcnt(n + 1, if (n % c == 0) xs else x :: xs)
    }(1, Nil).foldRight[List[A] => List[A]](identity)((x, kxs) => xs => kxs(x :: xs))(Nil)
  
//
//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))
  def split[A](c: Int, x: List[A]) = {
    type ListK = List[A] => (List[A], List[A])
    type ContK = (Int, ListK) => ListK
    x.foldRight[(List[A], ContK)]((Nil, (_, x) => x)) {
      (x, tp) => {val (acc, kcnt) = tp; (x :: acc, (n: Int, klst: ListK) =>
        if (n < c) kcnt(n + 1, xs => klst(x :: xs)) else xs => (klst(xs)._1, x :: acc))
    }}._2(0, x => (x, Nil))(Nil)
  }
}

memo.txt

昔に Tony Morris の blog を読んでやってみたアレ。
思ったより時間かかった。
継続を途中で打ち切るときに、未だにときどき混乱することがある。

TestMain.scala

// 車輪再発明従業員御用達 scalacheck

object Scala99Test {
  import org.scalacheck._
  import Arbitrary.arbitrary
  import Prop._  
  import Scala99._
  import Scala99StraightForward._
  
  val prop_last = 
    forAll{(xs: List[Int]) => xs.nonEmpty ==> (last(xs) == xs.last)}
  val prop_penultimate = 
    forAll{(xs: List[Int]) => (xs.size >= 2) ==> (penultimate(xs) == xs.init.last)}
  val prop_nth =
    forAll{(xs: List[Int], n: Int) => (0 until xs.size contains n) ==> (nth(n, xs) == xs(n))}
  val prop_length = 
    forAll{(xs: List[Int]) => length(xs) == xs.length}
  val prop_reverse =
    forAll{(xs: List[Int]) => reverse(xs) == xs.reverse}    
  val prop_isPalindrome = 
    forAll{(xs: List[Int]) => isPalindrome(xs) == (xs == xs.reverse)}  
  val prop_flatten = 
    forAll{(xs: List[Int], ys: List[List[Int]], zs: List[List[List[Int]]]) => {
      val arg = scala.util.Random.shuffle(xs ++ ys ++ zs)
      flatten(xs) == flatten2(xs)
    }}
  val prop_compress =
    forAll{(xs: List[Byte]) => compress(xs) == xs.foldRight(List[Byte]()){(e, l) =>
      if (l.headOption == Some(e)) l else e::l
    }}
  val prop_pack = 
    forAll{(xs: List[Byte]) => pack(xs) == pack2(xs) }
  val prop_encode = 
    forAll{(xs: List[Byte]) => encode(xs) == encode2(xs) }
  val prop_encodeModified = 
    forAll{(xs: List[Byte]) => encodeModified(xs) == encodeModified2(xs) }
  val prop_decode =
    forAll{(argxs: List[(Byte, Byte)]) =>
      val xs = argxs map {case(n, e) => (n: Int, e)}
      (decode(xs) == decode2(xs))
    }
  val prop_encodeDecodeIndentity =
    forAll{(xs: List[Byte]) => decode(encode(xs)) == xs}
  val prop_drop =
    forAll{(xs: List[Int], n: Int) => (n > 0) ==> (drop(n, xs) == drop2(n, xs))}
  val prop_dropUsingFoldRightTwice =
    forAll{(xs: List[Int], n: Int) => (n > 0) ==> (dropUsingFoldRightTwice(n, xs) == drop2(n, xs))}
  val prop_split =
    forAll{(xs: List[Int], n: Int) => split(n, xs) == xs.splitAt(n)}
  
  val props = Seq(
    prop_last,
    prop_penultimate,
    prop_length,
    prop_nth,
    prop_length,
    prop_reverse,
    prop_isPalindrome,
    prop_flatten,
    prop_compress,
    prop_pack,
    prop_encode,
    prop_encodeModified,
    prop_decode,
    prop_encodeDecodeIndentity,
    prop_drop,
    prop_dropUsingFoldRightTwice,
    prop_split,
    prop_reverse)

  def main(args: Array[String]) {
    props foreach (_.check)
  }
}

object Scala99StraightForward {
  def flatten2(xs: List[_]): List[Any] = xs flatMap {
    case l: List[_] => flatten2(l)
    case x => List(x)
  }  
  
  def pack2[A](arg: List[A]): List[List[A]] = arg match {
    case x :: xs => 
      val (ys, zs) = xs.span(x ==)
      (x :: ys) :: pack2(zs)
    case Nil => Nil
  }
  
  def encode2[A](xs: List[A]): List[(Int, A)] =
    pack2(xs) map { e => (e.length, e.head) }

  def encodeModified2[A](xs: List[A]): List[_] =
    pack2(xs) map {
      case e :: Nil => e
      case e :: es  => (1 + es.length, e)
    }
  
  def decode2[A](xs: List[(Int, A)]): List[A] =
    xs.flatMap {case (n, e) => List.fill(n)(e)}
  
  def drop2[A](n: Int, xs: List[A]): List[A] =
    xs.grouped(n).flatMap(_ take n - 1).toList
}