Scala exercises for beginners

id:akihiro4chawon 氏の scala を左傾化させる話 - akihiro4chawonの日記 が元ネタ

Pattern match*1 で解いてみた。
Pattern match は好きなのだが RWH によると明示的な再帰より fold を使う方がわかりやすいと書いてあった。この辺りは経験を積んでから判断したい。

object Exercises {
  def succ(n: Int) = n + 1
  def pred(n: Int) = n - 1

  // Exercise 1
  def add(x: Int, y: Int): Int = y match {
    case 0 => x
    case y => if (y > 0) add(succ(x), pred(y))
              else       add(pred(x), succ(y))
  }

  // Exercise 2
  def sum(x: List[Int]): Int = x match {
    case Nil   => 0
    case x::xs => add(x, sum(xs))
  }

  // Exercise 3
  def length[A](x: List[A]): Int = x match {
    case Nil   => 0
    case x::xs => succ(length(xs))
  }

  // Exercise 4
  def map[A, B](x: List[A], f: A => B): List[B] = x match {
    case Nil   => Nil
    case x::xs => f(x)::map(xs, f)
  }

  // Exercise 5
  def filter[A](x: List[A], f: A => Boolean): List[A] = x match {
    case Nil   => Nil
    case x::xs => if (f(x)) x::filter(xs, f)
                  else      filter(xs, f)
  }

  // Exercise 6
  def append[A](x: List[A], y: List[A]): List[A] = x match {
    case Nil   => y
    case x::xs => x::append(xs, y)
  }

  // Exercise 7
  def concat[A](x: List[List[A]]): List[A] = x match {
    case Nil   => Nil
    case x::xs => append(x, concat(xs))
  }

  // Exercise 8
  def concatMap[A, B](x: List[A], f: A => List[B]): List[B] = concat(map(x, f))

  // Exercise 9
  def maximum(x: List[Int]): Int = x match {
    case Nil    => Int.MinValue
    case x::Nil => x
    case x::xs  => x max maximum(xs)
  }

  // Exercise 10
  def reverse[A](x: List[A]): List[A] = {
    def rec(xs: List[A], ys: List[A]): List[A] = xs match {
      case Nil   => ys
      case x::xs => rec(xs, x::ys)
    }
    rec(x, Nil)
  }
}

object ExercisesTest {
  import org.scalacheck._
  import Arbitrary.arbitrary
  import Prop._  
  import Exercises._
  
//  val prop_add       = forAll((x: Int, y: Int) => add(x, y) == x + y)
//  val prop_sum       = forAll((xs: List[Int]) => sum(xs) == xs.sum)
  val prop_length    = forAll((xs: List[Int]) => length(xs) == xs.length)
  val prop_map       = forAll((xs: List[Int], f: Int => String) => map(xs, f) == xs.map(f))
  val prop_filter    = forAll((xs: List[Int], f: Int => Boolean) => filter(xs, f) == xs.filter(f))
  val prop_append    = forAll((xs: List[Int], ys: List[Int]) => append(xs, ys) == xs ++ ys)
  val prop_concat    = forAll((xs: List[List[Int]]) => concat(xs) == xs.flatten)
  val prop_concatMap = forAll((xs: List[Int], f: Int => List[String]) => concatMap(xs, f) == xs.flatMap(f))
  val prop_maximum   = forAll((xs: List[Int]) => xs.nonEmpty ==> (maximum(xs) == xs.max))
  val prop_reverse   = forAll((xs: List[Int]) => reverse(xs) == xs.reverse)
  
  val props = Seq(
//    prop_add,
//    prop_sum,
    prop_length,
    prop_map,
    prop_filter,
    prop_append,
    prop_concat,
    prop_concatMap,
    prop_maximum,
    prop_reverse)

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

ScalaCheck の部分は id:akihiro4chawon 氏のものをコピーしただけ。
prop_sum を実行すると返ってこないのは再帰が深すぎるから?
QuickCheck を勉強してから調べる。

あまり意味はないかもしれないが Pattern match で Nil を最初に置くのか後に置くのかどちらのスタイルが一般的なんだろう?
RWH では where 句がない場合は後ろに置かれている気がする。

関数型言語は Ninety-Nine XXX Problems とか良質な問題が多いので楽しい。

2011-05-29 追記

『Scheme 手習い』の add の方法で

  def add(x: Int, y: Int): Int = y match {
    case 0 => x
    case y => if (y > 0) succ(add(x, pred(y)))
              else       pred(add(x, succ(y)))
  }

*1:http://groovy.codehaus.org/Roadmap をみると Groovy では 2.0 で導入予定