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

2問解けなかった。

2015/6/3 Excercise 3.24は解けた

// 3.1
// A: 3

// 3.2
def tail[A](l: List[A]): List[A] = l match {
  case Nil => Nil
  case Cons(x, xs) => xs
}

// 3.3
def setHead[A](l: List[A], element: A): List[A] = l match {
  case Nil => Nil
  case Cons(x, xs) => Cons(element, xs)
}

// 3.4
def drop[A](l: List[A], n: Int): List[A] = {
  if (n == 0) l
  else {
    l match {
      case Nil => Nil
      case Cons(x, xs) => drop(xs, n - 1)
    }
  }
}

// 3.5
def dropWhile[A](l: List[A], p: A => Boolean): List[A] = l match {
  case Nil => Nil
  case Cons(x, xs) => if p(x) dropWhile(xs, p) else Cons(x, xs)
}

// 3.6
def init[A](l: List[A]): List[A] = l match {
  case Nil => Nil
  case Cons(x, Nil) => Nil
  case Cons(x, xs) => Cons(x, init(xs))
}
// A: リスト全体を走査する必要があるため、リストの長さに比例した時間がかかる。

// 3.7
// A: 以下のようにすれば、再起を中断して短絡させることができる。
// その理由は、無名関数内でのreturnはその呼び出し元の関数を終了させるからである。
def product3(ns: List[Double]):Double = foldRight(ns, 1.0) {
  (x, a) => 
    if (x == 0.0) return 0.0
    else x * a
}
// この仕様を利用すれば、同様にfoldRight中で短絡評価ができる。

// 3.8
// A: 同じ要素で同じ並び順のリストが返却される。
// このことは、Listのデータ構造とfoldRightの処理順は同じ構造であることを表している。

// 3.9
def length[A](l: List[A]): Int = foldRight(l, 0){ (x, a) => 1 + a }

// 3.10
def foldLeft[A, B](l: List[A], z: B)(f: (B, A) => B): B = l match {
  case Nil => z
  case Cons(x, xs) => foldLeft(xs, f(z, x))(f)
}

// 3.11
def sum(l: List[Int]): Int = foldLeft(l, 0)(_ + _)

def product(l: List[Double]): Double = foldLeft(l, 1.0)(_ * _)

def length[A](l: List[A]): Int = foldLeft(l, 0){ (a, x) => 1 + a }

// 3.12
def reverse[A](l: List[A]): List[A] = foldLeft(l, Nil: List[A]){ (a, x) => x :: a }

// 3.13
// 解けなかった。。。

// 3.14
def append[A](a1: List[A], a2: List[A]):List[A] = foldRight(a1, a2){ (x, a) => Cons(x, a) }

// 3.15
def appendAll[A](ls: List[List[A]]): List[A] = foldLeft(ls, Nil: List[A]){ (a, x) => append(a, x) }

// 3.16
def plusOne(l: List[Int]): List[Int] = foldRight(l, Nil: List[Int]){(x, a) => Cons(x + 1, a) }

// 3.17
def doubleToString(l: List[Double]): List[String] = foldRight(l, Nil: List[String]){(x, a) => Cons(x.toString, a) }

// 3.18
def map[A, B](as: List[A])(f: A => B): List[B] = foldRight(as, Nil: List[B]){(x, a) => Cons(f(x), a) }

// 3.19
def filter[A](as: List[A])(f: A => Boolean): List[A] = foldRight(as, Nil: List[A]){ (x, a) => if (f(x)) x :: a else a }

// 3.20
def flatMap[A, B](as: List[A])(f: A => List[B]): List[B] = foldRight(as, Nil: List[B]){ (x, a) => append(f(x), a) }

// 3.21
def filter2[A](as: List[A])(f: A => Boolean): List[A] = flatMap(as){ x => if(f(x)) List(x) else Nil }

// 3.22
def zipWithAdd(ns1: List[Int], ns2: List[Int]): List[Int] = (ns1, ns2) match {
  case (Nil, _) => Nil
  case (_, Nil) => Nil
  case (Cons(x, xs), Cons(y, ys)) => Cons(x + y, zipWithAdd(xs, ys))
}

// 3.23
def zipWith[A, B](as1: List[A], as2: List[A])(f: (A, A) => B): List[B] = (as1, as2) match {
  case (Nil, _) => Nil
  case (_, Nil) => Nil
  case (Cons(x, xs), Cons(y, ys)) => Cons(f(x, y), zipWith(xs, ys)(f))
}

// 3.24
def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = {
  def tails[A](as: List[A]): List[List[A]] = as match {
    case Nil => Nil
    case Cons(x, xs) => Cons(xs, tails(xs))
  }
  def startsWith[A](as1: List[A], as2: List[A]): Boolean = (as1, as2) match {
    case (Nil, Nil) => true
    case (Nil, Cons(_, _)) => false
    case (Cons(x, xs), Cons(y, ys)) => x == y && startsWith(xs, ys)
    case _ => false
  }
  foldRight(Cons(sup, tails(sup)), false) { case (x, a) =>
    startsWith(x, sub) || a
  }
}


// 3.25
def size[A](t: Tree[A]): Int = t match {
  case Leaf(_) => 1
  case Branch(l, r) => 1 + size(l) + size(r)
}

// 3.26
def maximum(t: Tree[Int]): Int = t match {
  case Leaf(v) => v
  case Branch(l, r) => maximum(l) max maximum(r)
}

// 3.27
def depth[A](t: Tree[A]): Int = t match {
  case Leaf(_) => 1
  case Branch(l, r) => 1 + (depth(l) max depth(r))
}

// 3.28
def map[A, B](t: Tree[A])(f: A => B): Tree[B] = t match {
  case Leaf(v) => Leaf(f(v))
  case Branch(l, r) => Branch(map(l)(f), map(r)(f))
}

// 3.29
def fold[A,B](t: Tree[A])(l: A => B)(b: (B,B) => B): B = t match {
  case Leaf(v) => l(v)
  case Branch(left, right) => b(fold(left)(l)(b), fold(right)(l)(b))
}