Scala関数型デザイン&プログラミング3章

chapter3.scala

/**
 * EXERCISE 3.1
 * 以下のマッチ式はどのような結果になるか
 */

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]

object List{
  def apply[A](as: A*): List[A] = if (as.isEmpty) Nil else Cons(as.head, apply(as.tail: _*))
}

object Match{
  def main(args: Array[String]): Unit ={
    val x = List(1,2,3,4,5) match{
      case Cons(x, Cons(2, Cons(4, _))) => x
      case Nil => 42
      case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y
      case _ => 101
    }
    println(x) // 3
  }
}

/**
 * EXERCISE 3.2
 * Listの最初の要素を削除する関数tailを実装せよ
 * (この関数の実行時間は一定になる)
 */

object ListTail {
  def tail[A](list: List[A]): List[A] = {
    list match{
      case Cons(_, x) => x
      case _ => Nil
    }
  }

  def main(args: Array[String]): Unit = {
    println(tail(List(1,2,3)))
  }
}

/**
 * EXERCISE 3.3
 * EXERCISE 3.2と同じ考え方に基づいて、Listの最初の要素を別の値と置き換えるsetHead関数を実装せよ
 */

object SetHead {
  def setHead[A](list: List[A], head: A): List[A] = {
    list match{
      case Cons(_, x) => Cons(head, x)
      case _ => Cons(head, Nil)
    }
  }

  def main(args: Array[String]): Unit ={
    println(setHead(List(1,2,3),10))
  }
}

/**
 * EXERCISE 3.4
 * tailを一般化してリストの先頭からn個の要素を削除するdropという関数に置き換えよ
 */

object ListDrop {
  def drop[A](l: List[A], n: Int): List[A] = {
    if(n == 0) l
    else l match{
      case Cons(_, x) => drop(x, n-1)
      case _ => throw new IllegalArgumentException
    }
  }

  def main(args: Array[String]): Unit ={
    try {
      println(drop(List(1, 2, 3), 2))
      println(drop(List(1, 2, 3), 3))
      println(drop(List(1, 2, 3), 4))
    }catch{
      case ex: IllegalArgumentException => println(ex)
    }
  }
}

/**
 * EXERCISE 3.5
 * 術後とマッチする場合に限り、Listからその要素までの要素を削除するdropWhileを実装せよ
 */

object DropWhile {
  def dropWhile[A](l: List[A], f: A => Boolean): List[A] = {
    l match{
      case Cons(x, y) if f(x) => y
      case Cons(_, y) => dropWhile(y, f)
      case Nil => Nil
    }
  }

  def main(args: Array[String]): Unit ={
    println(dropWhile(List(1,2,3,2), (x: Int) => (x % 2 == 0)))
    println(dropWhile(List(1,2,3,2), (x: Int) => (x == 4))) // Nilになってしまうぞ
  }
}

/**
 * EXERCISE 3.9
 * foldRightを使ってリストの長さを計算せよ。
 */
object FoldRight {
  def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B = {
    as match {
      case Nil => z
      case Cons(x, xs) => f(x, foldRight(xs, z)(f))
    }
  }

  def length[A](as: List[A]): Int = {
    foldRight(as, 0)((a,b) => b + 1)
  }

  def main(args: Array[String]): Unit ={
    println(length(List(9,8,4,1,2)))
  }
}

/**
 * EXERCISE 3.10
 * foldLeftの実装
 * (上のfoldRightの実装は末尾再帰でないためリストが大きい場合はStackOverFlowしてしまう。)
 */

object FoldLeft {
  def foldLeft[A,B](as: List[A], z: B)(f: (B, A) => B): B = {
    as match {
      case Nil => z
      case Cons(x, xs) => foldLeft(xs, f(z,x))(f)
    }
  }

  def main(args: Array[String]): Unit ={
    println(foldLeft(List(1,2,3), 0)((x,y) => x + y))
  }
}

/**
 * EXERCISE 3.12
 * 要素が逆に並んだリストを返す関数を記述せよ
 */

object ListReverse {
  def reverse[A](ls: List[A]): List[A] = {
    FoldLeft.foldLeft(ls, List[A]())((z, a) => Cons(a, z))
  }

  def main(args: Array[String]): Unit ={
    println(reverse(List(1, 2, 3)))
  }
}

/**
 * EXERCISE 3.13
 * foldLeftを使ってfoldRightを実装する
 * (foldRightを末尾再帰的に実装することができるようになり、StackOverFlowしなくなる)
 */

object FoldRightKai {
  def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B = {
    FoldLeft.foldLeft(ListReverse.reverse(as), z)((b: B, a: A) => f(a, b))
  }

  def length[A](as: List[A]): Int = {
    foldRight(as, 0)((a,b) => b + 1)
  }

  def main(args: Array[String]): Unit ={
    println(length(List(9,8,4,1,2)))
  }
}

/**
 *  EXERCISE 3.16
 *  各要素に1を足すことで整数のリストを変換する関数を記述せよ
 */

object ListPlusOne {
  def plusOne(ls: List[Int]): List[Int] ={
    ls match{
      case Nil => Nil
      case Cons(x, y) => Cons(x + 1, plusOne(y))
    }
  }

  def main(args: Array[String]): Unit ={
    println(plusOne(List(1,2,3,0,0,0)))
  }
}

sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

/**
 * EXERCISE 3.25
 * 2分木のノードの数を数えるsize関数を記述せよ
 */

object TreeSize{
  def size[A](tree: Tree[A]): Int ={
    tree match{
      case Branch(x, y) => size(x) + size(y)
      case Leaf(_) => 1
    }
  }

  def main(args: Array[String]): Unit ={
    println(size(Branch(Branch(Leaf(0), Leaf(0)), Leaf(0))))
  }
}