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)) }