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

前提

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

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

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

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

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

  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 の解答が参考になった:

  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] と一致していればソートされているという判断でいいだろう:

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 カリー化を実装せよ

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

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 を実装せよ

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

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

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

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

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() を参考にしてできた:

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

  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 と同様にして簡単にできた:

  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() を使うべきであることは思いついたので以下のように実装:

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 式を使うのだろうと思いついた。再帰も大分慣れてきた:

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

  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 文を書いていた。こちらの方がシンプルか:

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 式強力だな:

  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 を与えても何も変化しない:

  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 を使ってリストの長さを計算せよ

なんかパズルみたいだ:

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

解答と完全に一致。

EXERCISE 3.10 foldLeft を実装せよ

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

  @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() とほぼ同じなので楽勝:

  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 つのリストに移し替えれば逆順となる:

  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() を使用していた:

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

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

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

  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() でなければならない:

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

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

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

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

  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 を使用。
……と思ったけど解答を見たらあまりのシンプルさに負けた:

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

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

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

EXERCISE 3.17 各値を String に変換せよ

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

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

EXERCISE 3.18 map を定義せよ

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 を定義せよ

うーむ、脳トレだ:

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 を実装せよ

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 でラップするだけ？

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 つのリストの要素を足し合わせる処理を定義せよ

  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 の関数を整数及び加算に限定されないよう一般化せよ

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

  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 を使って何とか以下のように実装してみた:

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

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

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

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

  @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 関数を記述せよ

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

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

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

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 関数を記述せよ

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

  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 関数を記述せよ

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 関数を記述せよ

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 等をそれを用いて実装せよ

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

  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() する前にデータ型の変換を行う事ができるとコードが短くなるのでそういった時に使用するようだ。

参考になった。

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 をベースとしてのくだりの意味がわからなかったので愚直に実装してみた:

  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 しろという意図だった:

  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 を実装せよ

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

  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 を使用してもっとシンプルにしていた。うーむ、勉強になる:

  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 が使えるんだな。

  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 を参考にして以下実装:

  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 に各種メソッドを追加

  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 版を少し書き換えればいいだけ:

  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 extends Partial[A,Nothing]
case class Success+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 を実装せよ

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

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

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 が必要になってしまっているところがダサい。公式はもっとうまくやっている:

  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) を実装せよ

  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 を実装せよ

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

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

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

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

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 を実装せよ

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

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

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

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 関数を実装せよ

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

EXERCISE 5.9 from を実装せよ

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

EXERCISE 5.10 fibs を記述せよ

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

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

EXERCISE 5.11 unfold を実装せよ

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

  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 を実装せよ

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