Scala 関数型デザイン & プログラミングの練習問題で勉強

# 前提

**Scala 関数型デザイン & プログラミング ~ Scalaz コントリビューターによる関数型徹底ガイド**という本がある。こちらの練習問題を勉強の為に解いてみた。尚、原著の **Functional Programming in Scala** の方の解答が非常に簡易的なものながらも [GitHub に掲載されている](https://github.com/fpinscala/fpinscala)ので、こちらで答え合わせを行うことができる。

第 1 章は練習問題なし。第 2 章から行う。

# 第 2 章 Scala 関数型プログラミングの準備

## EXERCISE 2.1 n 番目のフィボナッチ数を取得する再帰関数を記述せよ

前提から以下のような再帰を書いてしまった:

```scala
  def fib(n: BigInt): BigInt = {
    require(n > 0)
    def go(n: BigInt): BigInt = {
      if (n == 1) 0 else if (n == 2) 1 else go(n - 2) + go(n - 1)
    }
    go(n)
  }
```

再帰関数の定義ではローカルな末尾再帰関数を使用せよと指示がある。つまり `@annotation.tailrec` を使えということだが、上記コードだと単純な末尾再帰になっていないので `@annotation.tailrec` を付与するとコンパイルが通らない。しかも 2 つの再帰呼び出しをしているので `n` の値が増えていくとメソッド呼び出しが指数関数的に増えていくので効率が悪い。

これは GitHub の解答が参考になった:

```scala
  def fib(n: BigInt): BigInt = {
    @annotation.tailrec
    def loop(n: BigInt, prev: BigInt, cur: BigInt): BigInt = {
      if (n == 0) prev else loop(n - 1, cur, prev + cur)
    }
    loop(n, 0, 1)
  }
```

## EXERCISE 2.2 Array[A] がソートされているかを調べる isSorted を実装せよ

要するにソートした後の `Array[A]` が元の `Array[A]` と一致していればソートされているという判断でいいだろう:

```scala
object Scala extends App {
  def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean = {
    as.sortWith(ordered).toSeq == as.toSeq
  }

  println(isSorted(Array(1, 2, 3), (x: Int, y: Int) => x < y))  // true
  println(isSorted(Array(2, 3, 1), (x: Int, y: Int) => x < y))  // false
  println(isSorted(Array("A", "BB", "CCC"), (x: String, y: String) => x.length < y.length))  // true
  println(isSorted(Array("BB", "CCC", "A"), (x: String, y: String) => x.length < y.length))  // false
}
```

解答も見てみたがそちらは上記のようなアプローチでなく再帰関数で自前のソートを行い 1 つ 1 つ判定していた。まぁ章の内容からするとそれが正しいのだろう……。

## EXERCISE 2.3 カリー化を実装せよ

シグネチャが書いてあるからできるが、無かったら厳しいというか、自分でメソッドを書いて後から見なおしても暗号が書いてあるようでつらいが、とりあえず以下のようにできた:

```scala
object Scala extends App {
  def curry[A, B, C](f: (A, B) => C): A => (B => C) = (a: A) => (b: B) => f(a, b)

  println(curry((_: Int) + (_: Int))(2)(3))  // 5
  println(curry((_: String).charAt(_: Int))("ABCDE")(2))  // C
}
```

解答も一致していたので良しとする。

## EXERCISE 2.4 カリー化を逆向きに行う uncurry を実装せよ

以下のように実装できたが、やはり暗号みたいだ:

```scala
def uncurry[A, B, C](f: A => B => C): (A, B) => C = f(_: A)(_: B)
```

## EXERCISE 2.5 2 つの関数を合成する高階関数を実装せよ

このあたりは簡単だった:

```scala
def compose[A, B, C](f: B => C, g: A => B): A => C = (a: A) => f(g(a))
```

# 第 3 章 関数型プログラミングのデータ構造

## EXERCISE 3.1 マッチ式の確認

`case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y` がヒットし `3` が返る。念のため動かして確認した。

## EXERCISE 3.2 List.tail() を実装せよ

不変リストから head をどうやって切り離すんだろう……と思っていたが実行してみたら非常に参考になった。実装自体は `List.sum()` を参考にしてできた:

```scala
  def tail[A](list: List[A]): List[A] = list match {
    case Nil => Nil
    case Cons(_, xs) => xs
  }
```

```scala
  val list = List(1, 2, 3, 4, 5)
  println(list)
  val list2 = List.tail(list)
  println(list2)
```

```
Cons(1,Cons(2,Cons(3,Cons(4,Cons(5,Nil)))))
Cons(2,Cons(3,Cons(4,Cons(5,Nil))))
```

要するに `List.tail()` は外側の不変オブジェクト `Cons` を外しているだけで内部の `Cons` は再利用している。Scala の標準ライブラリの `List` もこのような実装になっているとのこと。

## EXERCISE 3.3 List.setHead() を実装せよ

3.2 と同様にして簡単にできた:

```scala
  def setHead[A](list: List[A], head: A): List[A] = list match {
    case Nil => Cons(head, Nil)
    case Cons(_, xs) => Cons(head, xs)
  }
```

## EXERCISE 3.4 List.drop() を実装せよ

`List.tail()` を使うべきであることは思いついたので以下のように実装:

```scala
def drop[A](l: List[A], n: Int): List[A] = if (n == 0) l else drop(tail(l), n - 1)
```

解答を見たがそちらは `List.tail()` を再利用していなかった。いや、こちらのほうが美しいだろう。

## EXERCISE 3.5 dropWhile() を実装せよ

ちょっと詰まったが今まで同様に match 式を使うのだろうと思いついた。再帰も大分慣れてきた:

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

```scala
  val list = List(1, 2, 3, 4, 5)
  println(list)
  val list2 = List.dropWhile(list, (_: Int) == 2)  // 3, 4, 5
  println(list2)
```

GitHub の解答を見ると再帰を使わずに case 式の方に if 文を書いていた。こちらの方がシンプルか:

```scala
def dropWhile[A](l: List[A], f: A => Boolean): List[A] = l match {
  case Cons(h,t) if f(h) => dropWhile(t, f)
  case _ => l
}
```

## EXERCISE 3.6 init() を実装せよ

なんか難しいのかと思ったらあっさりできた。`match` 式強力だな:

```scala
  def init[A](l: List[A]): List[A] = l match {
    case Cons(x, Nil) => Nil
    case Cons(x, xs) => Cons(x, init(xs))
  }
```

再帰呼び出しになるので実行時間はリストの長さに依存する。実装できないのは単方向リストだから。具体的には以前の例のように

```
Cons(1,Cons(2,Cons(3,Cons(4,Cons(5,Nil)))))  // List(1, 2, 3, 4, 5)
```

のような表現になっており, これを `Cons(1,Cons(2,Cons(3,Cons(4, Nil))))` に変えるのに最深部の `Cons` まで辿らなければならないから。

## EXERCISE 3.7 再帰で 0.0 を検出した際に再帰を中止して 0.0 を返せるか

`product()` 内で対象リスト内に 0.0 があるかどうかをチェックし, あったら直ちに 0.0 を返せば可能……だがこれだと再帰 (foldRight) 実行していないし。foldRight の実装を変更しないと「直ちに再帰を中止して」はできない?

GitHub に英語で解答らしきことがかいてあった:

>No, this is not possible! The reason is because _before_ we ever call our function, `f`, we evaluate its argument,
  which in the case of `foldRight` means traversing the list all the way to the end. We need _non-strict_ evaluation
  to support early termination---we discuss this in chapter 5.

>いや、返せない！何故なら関数 `f` を呼ぶ前に `foldRight` がリストを最後まで走査する場合に我々が引数を評価するからだ。我々が素早い終了をサポートするのに厳格でない評価を必要とする……これは 5 章で議論する。

ということなのでよくわからないが当たっているようだ。

## EXERCISE 3.8 Nil および Cons 自体を foldRight に渡した場合はどうなるか

Nil を与えても何も変化しない:

```scala
  val list = List(1, 2, 3)
  println(list)  // Cons(1,Cons(2,Cons(3,Nil)))
  val list2 = List.foldRight(list, Nil: List[Int])(Cons(_, _))
  println(list2)  // Cons(1,Cons(2,Cons(3,Nil)))
```

これが foldRight と List のデータコンストラクタとの関係について何を表しているか……とのことだが、よくわからない。解答を見てみる。

>We get back the original list! Why is that? As we mentioned earlier, one way of thinking about what `foldRight` "does"
  is it replaces the `Nil` constructor of the list with the `z` argument, and it replaces the `Cons` constructor with
  the given function, `f`. If we just supply `Nil` for `z` and `Cons` for `f`, then we get back the input list.

>（実行したら）元と同じリストを得た！何故か？簡単に言うと `foldRight` は `Nil` というリストのコンストラクタを `z` 引数を以って置き換える方法の 1 つと考えられるからだ。そして Nil は `f` 関数で与えられた `Cons` コンストラクタで置き換えられる。もし `z` 引数で `Nil` を与え `Cons` を `f` 関数で与えた場合、入力したリストをそのまま受け取る。

……。よくわからん。

## EXERCISE 3.9 foldRight を使ってリストの長さを計算せよ

なんかパズルみたいだ:

```scala
  def length[A](as: List[A]): Int = foldRight(as, 0)((_, b) => b + 1)
```

解答と完全に一致。

## EXERCISE 3.10 foldLeft を実装せよ

そもそも巨大な List を new する時点で StackOverFlow になるんだが……。ここは降参した:

```scala
  @annotation.tailrec
  def foldLeft[A,B](l: List[A], z: B)(f: (B, A) => B): B = l match {
    case Nil => z
    case Cons(h,t) => foldLeft(t, f(z,h))(f)
  }
```

## EXERCISE 3.11 foldLeft を用いた実装をせよ

`foldLeft()` さえ出来てしまえば後の実装は `foldRight()` とほぼ同じなので楽勝:

```scala
  def sum3(ns: List[Int]): Int = {
    foldLeft(ns, 0)(_ + _)
  }
  def product3(ns: List[Double]) = {
    foldLeft(ns, 1.0)(_ * _)
  }
  def length2[A](as: List[A]): Int = foldLeft(as, 0)((b, _) => b + 1)
```

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

`Cons` の実装が右から生成していき左から容易に要素を外せる実装になっているので、以下のようにもう 1 つのリストに移し替えれば逆順となる:

```scala
  def reverse[A](list: List[A]): List[A] = {
    def f(src: List[A], dst: List[A]): List[A] = src match {
      case Nil => dst
      case Cons(x, xs) => f(xs, Cons(x, dst))
    }
    f(list, List())
  }
```

「畳み込みを使って記述できるかどうかを確認せよ」……の畳み込みって何だろう。わからない。
解答を見てみたら `foldLeft()` を使用していた:

```scala
def reverse[A](l: List[A]): List[A] = foldLeft(l, List[A]())((acc,h) => Cons(h,acc))
```

## EXERCISE 3.13 foldRight をベースとして foldLeft 記述可能か

**難問**と書いてあるのだが要するにリストを逆順にして適用すれば良いということか。解答を参照した:

```scala
  def foldRightViaFoldLeft[A,B](l: List[A], z: B)(f: (A,B) => B): B =
    foldLeft(reverse(l), z)((b,a) => f(a,b))

  def foldRightViaFoldLeft_1[A,B](l: List[A], z: B)(f: (A,B) => B): B =
    foldLeft(l, (b:B) => b)((g,a) => b => g(f(a,b)))(z)

  def foldLeftViaFoldRight[A,B](l: List[A], z: B)(f: (B,A) => B): B =
    foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))(z)
```

一番上の例は分かるが下の暗号が分からない。確かに難問だ。

## EXERCISE 3.14 append を実装せよ

`foldLeft()` だとリストを取り出した際に逆順になってしまうので `foldRight()` でなければならない:

```scala
def append[A](list: List[A], x: A): List[A] = foldRight(list, List(x))(Cons(_, _))
```

これは解答と一致。しかし解答だと append 対象が `A` でなく `List[A]` になっている。一般的に `A` が想定されるのでは。

## EXERCISE 3.15 複数のリストからなるリストを 1 つのリストとして連結せよ

**難問**と書いてあるが既に定義した関数を使っていいのならそんなに難しくない気がする:

```scala
  def join[A](args: List[List[A]]): List[A] = {
    def f(src: List[List[A]], dst: List[A] = List()): List[A] = {
      if (length(src) == 0) dst else f(tail(src), append(dst, head(src)))
    }
    f(args)
  }
```

`length` と `tail` と `append` と `head` を使用。
……と思ったけど解答を見たらあまりのシンプルさに負けた:

```scala
def concat[A](l: List[List[A]]): List[A] = foldRight(l, Nil:List[A])(append)
```

## EXERCISE 3.16 各要素に 1 を足す関数を記述せよ

```scala
def add1(l: List[Int]): List[Int] = foldRight(l, Nil: List[Int])((a, b) => Cons(a + 1, b))
```

## EXERCISE 3.17 各値を String に変換せよ

`foldRight()` に大分慣れてきた。

```scala
def doubleToString(l: List[Double]): List[String] = foldRight(l, Nil: List[String])((a, b) => Cons(a.toString, b))
```

## EXERCISE 3.18 map を定義せよ

```scala
def map[A, B](as: List[A])(f: A => B): List[B] = foldRight(as, Nil: List[B])((a, b) => Cons(f(a), b))
```

## EXERCISE 3.19 filter を定義せよ

うーむ、脳トレだ:

```scala
def filter[A](as: List[A])(f: A => Boolean): List[A] = foldRight(as, Nil: List[A])((a, b) => if (f(a)) Cons(a, b) else b)

println(List.filter(List((1 to 100) : _*))(x => x % 2 == 0))  // 2, 4, ..., 100
```

## EXERCISE 3.20 flatMap を実装せよ

```scala
def flatMap[A, B](as: List[A])(f: A => List[B]): List[B] = foldRight(as, Nil: List[B])((a, b) => append(f(a), b))
```

## EXERCISE 3.21 flatMap を使って filter を実装せよ

前の `filter` を `List` でラップするだけ？

```scala
def filter2[A](as: List[A])(f: A => Boolean): List[A] = flatMap(as)(a => if (f(a)) List(a) else Nil)
```

## EXERCISE 3.22 2 つのリストの要素を足し合わせる処理を定義せよ

```scala
  def forEachAddition(list1: List[Int], list2: List[Int]): List[Int] = (list1, list2) match {
    case (Nil, _) => Nil
    case (_, Nil) => Nil
    case (Cons(x, xs), Cons(y, ys)) => Cons(x + y, forEachAddition(xs, ys))
  }
```

## EXERCISE 3.23 3.22 の関数を整数及び加算に限定されないよう一般化せよ

元となっているメソッドがあればあとはそこを関数に置き換えるだけだから簡単:

```scala
  def zipWith[A](list1: List[A], list2: List[A])(f: (A, A) => A): List[A] = (list1, list2) match {
    case (Nil, _) => Nil
    case (_, Nil) => Nil
    case (Cons(x, xs), Cons(y, ys)) => Cons(f(x, y), zipWith(xs, ys)(f))
  }
```

## EXERCISE 3.24 List に別の List が含まれているかを調べるメソッドを実装せよ

まず対象リストの全てのサブシーケンスを返すメソッドを実装する。`flatMap` を使って何とか以下のように実装してみた:

```scala
  private def getSubsequences[A](list: List[A]): Seq[List[A]] = {
    list.indices.flatMap(i => (i + 1 to list.length).map(list.slice(i, _)))
  }
```

これを使えば単に含まれているかを調べれば良くなる:

```scala
  def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = {
    getSubsequences(sup).contains(sub)
  }
```

だがこの実装だと「すべてのサブリストを返す」からリストがある程度大きくなると極端にパフォーマンスが落ちるだろうな……。
公式の解答は以下だった:

```scala
  @annotation.tailrec
  def startsWith[A](l: List[A], prefix: List[A]): Boolean = (l,prefix) match {
    case (_,Nil) => true
    case (Cons(h,t),Cons(h2,t2)) if h == h2 => startsWith(t, t2)
    case _ => false
  }
  @annotation.tailrec
  def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = sup match {
    case Nil => sub == Nil
    case _ if startsWith(sup, sub) => true
    case Cons(h,t) => hasSubsequence(t, sub)
  }
```

なるほどとしか言いようが無い。まだまだ修行が足りない。

## EXERCISE 3.25 Leaf と Branch を数える size 関数を記述せよ

```scala
sealed trait Tree[+A] {
  def size(): Int = {
    if (isInstanceOf[Leaf[A]]) {
      1
    } else if (isInstanceOf[Branch[A]]) {
      val branch = asInstanceOf[Branch[A]]
      1 + branch.left.size + branch.right.size
    } else {
      throw new IllegalStateException
    }
  }
}
```

```scala
object Scala extends App {
  val tree = Branch(Branch(Leaf("1"), Leaf("2")), Branch(Leaf("3"), Leaf("4")))
  print(tree.size())  // 7
}
```

公式を見たら Scala ではこういうのは `isInstanceOf` でなくパターンマッチを使うものなのだと勉強になった:

```scala
sealed trait Tree[+A] {
  def size(): Int = this match {
    case Leaf(_) => 1
    case Branch(l, r) => 1 + l.size() + r.size()
  }
}
```

## EXERCISE 3.26 maximum 関数を記述せよ

前問を参考に少し書き換えれば簡単:

```scala
  def maximum(tree: Tree[Int]): Int = tree match {
    case Leaf(x) => x
    case Branch(l, r) => maximum(l).max(maximum(r))
  }
```

## EXERCISE 3.27 depth 関数を記述せよ

```scala
sealed trait Tree[+A] {
  def depth: Int = this match {
    case Leaf(_) => 0
    case Branch(l, r) => 1 + l.depth.max(r.depth)
  }
}
```

## EXERCISE 3.28 map 関数を記述せよ

```scala
sealed trait Tree[+A] {
  def map[B](f: A => B): Tree[B] = this match {
    case Leaf(x) => Leaf(f(x))
    case Branch(l, r) => Branch(l.map(f), r.map(f))
  }
}
```

どうでもいいけど公式は `Tree` のメソッドでなくヘルパー関数として定義しているから使うとき不自然。

## EXERCISE 3.29 fold を定義し size 等をそれを用いて実装せよ

難しい。公式の解答を見て終わりにする:

```scala
  def fold[A,B](t: Tree[A])(f: A => B)(g: (B,B) => B): B = t match {
    case Leaf(a) => f(a)
    case Branch(l,r) => g(fold(l)(f)(g), fold(r)(f)(g))
  }
  
  def sizeViaFold[A](t: Tree[A]): Int = 
    fold(t)(a => 1)(1 + _ + _)
  
  def maximumViaFold(t: Tree[Int]): Int = 
    fold(t)(a => a)(_ max _)
  
  def depthViaFold[A](t: Tree[A]): Int = 
    fold(t)(a => 0)((d1,d2) => 1 + (d1 max d2))

  def mapViaFold[A,B](t: Tree[A])(f: A => B): Tree[B] = 
    fold(t)(a => Leaf(f(a)): Tree[B])(Branch(_,_))
```

# 第 4 章 例外を使わないエラー処理

## EXERCISE 4.1 Option の各メソッドを実装せよ

まず `Option.map()` と `Option.flatMap()` の挙動を理解していなかったのでそれらが実装できなかった。他は何とかなったが。`Option.getOrElse()` する前にデータ型の変換を行う事ができるとコードが短くなるのでそういった時に使用するようだ。

http://qiita.com/takudo/items/dca70d8b2a639a7663d9

参考になった。

```scala
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] = map(f).getOrElse(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 None => ob
    case _ => this
  }
  def filter(f: A => Boolean): Option[A] = this match {
    case Some(x) if f(x) =>  this
    case _ => None
  }
}
```

## EXERCISE 4.2 flatMap をベースとして variance 関数を実装せよ

flatMap をベースとしてのくだりの意味がわからなかったので愚直に実装してみた:

```scala
  def variance(xs: Seq[Double]): Option[Double] = {
    val m = xs.sum / xs.length
    Some(xs.map(x => math.pow(x - m, 2)).sum / xs.length)
  }
```

公式の解答は以下。`mean` 関数を使っている……。`mean` が `Option[A]` を返すのでそこから `flatMap` しろという意図だった:

```scala
  def mean(xs: Seq[Double]): Option[Double] =
    if (xs.isEmpty) None
    else Some(xs.sum / xs.length)

  def variance(xs: Seq[Double]): Option[Double] =
    mean(xs) flatMap (m => mean(xs.map(x => math.pow(x - m, 2))))
```

## EXERCISE 4.3 map2 を実装せよ

これはシンプルに実装できた:

```scala
  def map2[A, B, C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] = (a, b) match {
    case (Some(x), Some(y)) => Some(f(x, y))
    case _ => None
  }
```

と思ったら公式は以下のように `flatMap` を使用してもっとシンプルにしていた。うーむ、勉強になる:

```scala
  def map2[A,B,C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] =
    a flatMap (aa => b map (bb => f(aa, bb)))
```

## EXERCISE 4.4 sequence を実装せよ

解答読んでもよく分からん。やばい。`flatMap` の理解が怪しい。再帰でリストの先頭から関数を適用していくのに `flatMap` が使えるんだな。

```scala
  def sequence[A](a: List[Option[A]]): Option[List[A]] = a match {
    case Nil => Some(Nil)
    case h :: t => h.flatMap(hh => sequence(t).map(hh :: _))
  }
```

## EXERCISE 4.5 traverse を実装せよ

前問の `sequence` を参考にして以下実装:

```scala
  def traverse[A, B](a: List[A])(f: A => Option[B]): Option[List[B]] = a match {
    case Nil => None
    case h :: t => f(h).flatMap(hh => traverse(t)(f).map(hh :: _))
  }
```

## EXERCISE 4.6 Either に各種メソッドを追加

```scala
  def map[B](f: A => B): Either[E, B] = this match {
    case Right(a) => Right(f(a))
    case Left(e) => Left(e)
  }
  def flatMap[EE >: E, B](f: A => Either[EE, B]): Either[EE, B] = this match {
    case Right(a) => f(a)
    case Left(e) => Left(e)
  }
  def orElse[EE >: E, B >: A](b: => Either[EE, B]): Either[EE, B] = this match {
    case Left(a) => Left(a)
    case _ => b
  }
  def map2[EE >: E, B, C](b: Either[EE, B])(f: (A, B) => C): Either[EE, C] = {
    flatMap(aa => b.map(bb => f(aa, bb)))
  }
```

## EXERCISE 4.7 Either に sequence と traverse 実装

Option 版を少し書き換えればいいだけ:

```scala
  def sequence[E, A](es: List[Either[E, A]]): Either[E, List[A]] = es match {
    case Nil => Right(Nil)
    case h :: t => h.flatMap(hh => sequence(t).map(hh :: _))
  }
  def traverse2[E, A, B](as: List[A])(f: A => Either[E, B]): Either[E, List[B]] = as match {
    case Nil => Right(Nil)
    case h :: t => f(h).flatMap(hh => traverse2(t)(f).map(hh :: _))
  }
```

## EXERCISE 4.8 両方のエラーを報告するには?

`map2` が双方の引数として `Left[E]` が与えられていたら merge を行わないのが問題なので何らかの方法、改行区切りなどでメッセージを join するような実装にする。公式には独自の構造を作ってどうのこうのと書いてあるな:

> There are a number of variations on `Option` and `Either`. If we want to accumulate multiple errors, a simple
  approach is a new data type that lets us keep a list of errors in the data constructor that represents failures:
  
> trait Partial[+A,+B]
  case class Errors[+A](get: Seq[A]) extends Partial[A,Nothing]
  case class Success[+B](get: B) extends Partial[Nothing,B]
  
> There is a type very similar to this called `Validation` in the Scalaz library. You can implement `map`, `map2`,
  `sequence`, and so on for this type in such a way that errors are accumulated when possible (`flatMap` is unable to
  accumulate errors--can you see why?). This idea can even be generalized further--we don't need to accumulate failing
  values into a list; we can accumulate values using any user-supplied binary function.
  
> It's also possible to use `Either[List[E],_]` directly to accumulate errors, using different implementations of
  helper functions like `map2` and `sequence`.

# 第 5 章 正格と遅延

## EXERCISE 5.1 toList を実装せよ

```scala
  def toList: List[A] = this match {
    case Empty => Nil
    case Cons(h, t) => h() :: t().toList
  }
```

公式のがコード量が多いが `@annotation.tailrec` を使えているのでこちらの方が高速だろう:

```scala
def toList: List[A] = {
    @annotation.tailrec
    def go(s: Stream[A], acc: List[A]): List[A] = s match {
      case Cons(h,t) => go(t(), h() :: acc)
      case _ => acc
    }
    go(this, List()).reverse
  }
```

## EXERCISE 5.2 take(n) と drop(n) を実装せよ

`take` が `reverse` が必要になってしまっているところがダサい。公式はもっとうまくやっている:

```scala

  def take(n: Int): Stream[A] = {
    @annotation.tailrec
    def go(src: Stream[A], dst: Stream[A], count: Int): Stream[A] = {
      if (count == 0) {
        dst
      } else src match {
        case Empty => dst
        case Cons(h, t) => go(t(), Stream.cons(h(), dst), count - 1)
      }
    }
    go(this, Stream(), n).reverse()
  }

  def drop(n: Int): Stream[A] = {
    @annotation.tailrec
    def go(stream: Stream[A], count: Int): Stream[A] = {
      if (count == 0) {
        stream
      } else stream match {
        case Empty => stream
        case Cons(h, t) => go(t(), count - 1)
      }
    }
    go(this, n)
  }

  def reverse(): Stream[A] = {
    @annotation.tailrec
    def go(src: Stream[A], dst: Stream[A]): Stream[A] = src match {
      case Empty => dst
      case Cons(h, t) => go(t(), Stream.cons(h(), dst))
    }
    go(this, Stream())
  }
```

## EXERCISE 5.3 takeWhile(p) を実装せよ

```scala
  def takeWhile(p: A => Boolean): Stream[A] = this match {
    case Cons(h, t) if p(h()) => Stream.cons(h(), t().takeWhile(p))
    case Cons(_, t) => t().takeWhile(p)
    case _ => this
  }
```

## EXERCISE 5.4 forAll を実装せよ

```scala
  def forAll(p: A => Boolean): Boolean = this match {
    case Cons(h, t) if p(h()) => t().forAll(p)
    case Cons(_, _) => false
    case _ => true
  }
```

公式の解答がシンプルだ:

```scala
def forAll(f: A => Boolean): Boolean =
    foldRight(true)((a,b) => f(a) && b)
```

## EXERCISE 5.5 foldRight を使用して takeWhile を実装せよ

```scala
def takeWhile2(p: A => Boolean): Stream[A] = foldRight(Stream[A]())((a, b) => if (p(a)) Stream.cons(a, b) else b)
```

## EXERCISE 5.6 foldRight を使用して headOption を実装せよ

難問だそうなので答えを見る:

```scala
def headOption: Option[A] = foldRight(None: Option[A])((h,_) => Some(h))
```

## EXERCISE 5.7 map, filter, append, flatMap を実装せよ

```scala
def map[B](f: A => B): Stream[B] = foldRight(Stream.empty[B])((a, b) => Stream(f(a)))
def filter(f: A => Boolean): Stream[A] = foldRight(Stream.empty[A])((a, b) => if (f(a)) Stream.cons(a, b) else b)
def append[B >: A](a: => Stream[B]): Stream[B] = foldRight(a)(Stream.cons(_, _))
def flatMap[B](f: A => Stream[B]): Stream[B] = foldRight(Stream.empty[B])((h, t) => f(h).append(t))
```

## EXERCISE 5.8 constant 関数を実装せよ

```scala
def constant[A](a: A): Stream[A] = {
  lazy val ones: Stream[A] = Cons(() => a, () => ones)
  ones
}
```

## EXERCISE 5.9 from を実装せよ

```scala
def from(n: Int): Stream[Int] = cons(n, from(n + 1))
```

## EXERCISE 5.10 fibs を記述せよ

降参した。公式がシンプル過ぎてもう辛い:

```scala
  val fibs = {
    def go(x: Int, y: Int): Stream[Int] = cons(x, go(y, x + y))
    go(0, 1)
  }
```

## EXERCISE 5.11 unfold を実装せよ

難しすぎる。公式をみる:

```scala
  def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A] = f(z) match {
    case Some((h, s)) => cons(h, unfold(s)(f))
    case None => empty
  }
```

## EXERCISE 5.12 unfold で fibs, from, constant, ones を実装せよ

```scala
  val fibs2 = unfold((0, 1)) {
    case (f0, f1) => Some((f0, (f1, f0 + f1)))
  }
  def from2(n: Int) = unfold(n)(n => Some((n, n + 1)))
  def constant2[A](a: A) = unfold(a)(_ => Some((a, a)))
  val ones2 = unfold(1)(_ => Some((1, 1)))
```