Scala関数型デザイン＆プログラミング - Scalazコントリビューターによる関数型徹底ガイドの課題をやってみた

目次

第2章と第3章、第4章（最初の方だけ）のいくつかを試しに実施してみました。
※関数部分しか掲載しておりません。

1.【第2章】

  // Exercise 2.1
  // n 番目のフィボナッチ数※10 を取得する再帰関数を記述せよ。最初の2 つのフィボナッチ数は0 と 1 である。
  // n 番目の数字は常に前の2 つの数字の合計となる。この数列は0、1、1、2、3、5 のように始まる。
  // 再帰関数の定義では、ローカルな末尾再帰関数を使用すること。
  def fib(n: Int): Int = {
    @annotation.tailrec
    def loop(prev: Int, curr: Int, pos: Int): Int = {
      if (pos == 0)
        prev
      else
        loop(curr, prev + curr, pos - 1)
      }
      loop(0, 1, n)
  }

  // Exercise 2.2
  // 指定された比較関数に従ってArray[A] がソートされているかどうかを調べるisSorted を実装せよ。
  def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean = {
    @annotation.tailrec
    def loop(n: Int): Boolean = {
      if (n >= as.length - 1)
        true
      else if (ordered(as(n), as(n + 1)))
        loop(n + 1)
      else
        false
    }
    loop(0)
  }

  // Exercise 2.3
  // カリー化（currying）※17 では、引数2 つの関数f が、f を部分的に適用する引数1 つの関数に変換される。
  //この場合も、コンパイルできる実装は1 つだけである。この実装を記述せよ。
  def curry[A, B, C](f: (A, B) => C): A => (B => C) = {
    a => b => f(a, b)
  }

  // Exercise 2.4
  // curry による変換を逆向きに行うuncurry を実装せよ。
  // => は右結合であるため、A => (B => C)はA => B => C と記述できる。
  def uncurry[A, B, C](f: A => B => C): (A, B) => C = {
    (a, b) => f(a)(b)
  }

  // Exercise 2.5
  // 2 つの関数を合成する高階関数を実装せよ。
  def compose[A, B, C](f: B => C, g: A => B): A => C = {
    a => f(g(a))
  }

2.【第3章】

  // Exercise 3.2
  // List の最初の要素を削除する関数tail を実装せよ。
  // この関数の実行時間が一定であることに注意。
  // List がNil である場合、実装上の選択肢として他に何があるか。
  //この質問については、次章で再び取り上げる。
  def tail[A](as: List[A]): List[A] = as match {
    case Nil => Nil
    case Cons(_, tail) => tail
  }

  // Exercise 3.5
  // 述語とマッチする場合に限り、List からその要素までの要素を削除するdropWhile を実装せよ。
  def dropWhile[A](as: List[A], f: A => Boolean): List[A] = as match {
    case Cons(head, tail) if f(head) => dropWhile(tail, f)
    case _ => as
  }

  // Exercise 3.6
  // すべてがこのようにうまくいくわけではない。
  // List の末尾を除くすべての要素で構成されたListを返すinit 関数を実装せよ。
  // List(1,2,3,4) が与えられた場合、init はList(1,2,3) を返す。
  // この関数をtail のように一定時間で実装できないのはなぜか。
  def init[A](as: List[A]): List[A] = as match {
    case Nil => Nil
    case Cons(head, Nil) => Nil
    case Cons(head, tail) => Cons(head, init(tail))
  }

  // Exercise 3.9
  // foldRight を使ってリストの長さを計算せよ。
  def length[A](as: List[A]): Int = List.foldRight(as, 0)((_, y) => 1 + y)

  // Exercise 3.10
  // このfoldRight の実装は末尾再帰ではなく、リストが大きい場合はStackOverflowError になってしまう。
  // これをスタックセーフではないと言う。
  // そうした状況であると仮定し、前章で説明した手法を使って、リスト再帰の総称関数foldLeft を記述せよ※17。
  // シグネチャは以下のとおり。
  @annotation.tailrec
  def foldLeft[A, B](as: List[A], z: B)(f: (B, A) => B): B = as match {
    case Nil => z
    case Cons(head, tail) => foldLeft(tail, f(z, head))(f)
  }

  // Exercise 3.11
  // 整数のリストの要素の総和を返す関数を実装せよ。
  // ただし foldLeft をつかって実装してください
  def sum(ints: List[Int]): Int = foldLeft(ints, 0)(_ + _)

  // Exercise 3.11
  // 整数のリストの要素の総積を返す関数を実装せよ。
  def product(ints: List[Int]): Int = foldLeft(ints, 1)(_ * _)

  // Exercise 3.18
  // リストの各要素を変更し、かつリストの構造をそのまま保つ総称関数map を記述せよ。
  // この関数のシグネチャは以下のとおり※18。
  def map[A, B](as: List[A])(f: A => B): List[B] = as match {
    case Nil => Nil
    case Cons(head, tail) => Cons(f(head), map(tail)(f))
  }

  // Exercise 3.20
  // map と同じような働きをするflatMap 関数を記述せよ。
  // この関数は単一の結果ではなくリストを返し、そのリストは最終的な結果のリストに挿入されなければならない。
  // この関数のシグネチャは以下のとおり。
  // def flatMap[A,B](as: List[A])(f: A => List[B]): List[B]
  // たとえばflatMap(List(1,2,3))(i => List(i,i)) はList(1,1,2,2,3,3) になるはずである。
  def flatMap[A, B](as: List[A])(f: A => List[B]): List[B] = {
    def loop(as: List[A]): List[B] = as match {
      case Nil => Nil
      case Cons(head, tail) => append(f(head), loop(tail))
    }
    def append[A](al: List[A], bl: List[A]): List[A] = al match {
      case Nil => bl
      case Cons(head, tail) => Cons(head, append(tail, bl))
    }
    loop(as)
  }

  // Exercise 3.21
  // flatMap を使ってfilter を実装せよ。
  def filter[A](as: List[A])(f: A => Boolean): List[A] = flatMap(as)(x => if(f(x)) List(x) else Nil)

  // Exercise 3.23
  // EXERCISE 3.22 で作成した関数を、整数または加算に限定されないように一般化せよ。
  // 一般化された関数にはzipWith という名前を付けること。
  def zipWith[A, B](as: List[A], bs: List[A])(f: (A, A) => B): List[B] = (as, bs) match {
    case (Nil, _) => Nil
    case (_, Nil) => Nil
    case (Cons(ahead, atail), Cons(bhead, btail)) => Cons(f(ahead, bhead), zipWith(atail, btail)(f))
  }

3.【第4章】

// Exercise 4.1
// リスト4-4 のすべての関数をOption で実装せよ。
// 各関数を実装するときに、その関数の意味と、それを使用するであろう状況について考えること。
// どの関数をいつ使用するかについては、後ほど考察する。
// この練習問題を解くためのヒントは以下のとおり。
// ●● パターンマッチングを使用してもかまわないが、mapとgetOrElseを除く関数はすべてパターンマッチングに頼らなくても実できるはずである。
// ●● mapとflatMapの実装は、型シグネチャの情報に基づいて十分に決定できるはずである。
// ●● getOrElseはOptionのSomeケースの結果を返す。OptionがNoneの場合は、指定されたデフォルト値を返す。
// ●● orElseは、1つ目のOptionが定義されている場合はそれを返し、そうでない場合は2つ目のOption を返す。

trait Option[+A] {
  def map[B](f: A => B): Option[B] = this match {
    case Some(x) => Some(f(x))
    case None => None
  }

  def flatMap[B](f: A => Option[B]): Option[B] = this match {
    case Some(x) => f(x)
    case None => None
  }

  def getOrElse[B >: A](default: => B): B = this match {
    case Some(x) => x
    case None => default
  }

  def orElse[B >: A](ob: => Option[B]): Option[B] = this match {
    case _ => this
    case None => ob
  }

  def filter(f: A => Boolean): Option[A] = this match {
    case Some(x) if f(x) => Some(x)
    case _ => None
  }
}

case class Some[+A](get: A) extends Option[A]
case object None extends Option[Nothing]

// Exercise 4.2
// flatMap をベースとしてvariance 関数を実装せよ。
// シーケンスの平均をm、シーケンスの各要素をx とすれば、分散※8 はmath.pow(x - m, 2) の平均となる。
def variance(xs: Seq[Double]): Option[Double] = mean(xs).flatMap(x => mean(xs.map(y => math.pow(y - x, 2))))
def mean(xs: Seq[Double]): Option[Double] = if(xs.isEmpty) None else Some(xs.sum / xs.length)

// Exercise 4.3
// 2項関数を使ってOption型の2つの値を結合する総称関数map2を記述せよ。
// どちらかのOption値がNoneの場合は、戻り値もNoneになる。
def map2[A,B,C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] = (a, b) match {
  case (_, None) => None
  case (None, _) => None
  case(Some(a), Some(b)) => Some(f(a, b))
}

このExerciseを実施しただけでも大分関数型がしみ込んできた気がします。 そして関数型の考え的なところもある程度分かったつもりになってきました（笑）