"Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド"を買いました。
ちょっとずつ読んで、各章の内容をまとめてゆきます。

Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド (impress top gear)

Paul Chiusano (著),Rúnar Bjarnason (著),株式会社クイープ (翻訳)

Amazon

今回は5章。遅延評価のところです。

5章

この章では非正格性、要は遅延評価周りを扱います。
この辺は凄く関数型っぽいですね。
実行効率にも大きく関与する部分ですし、しっかりと進めてゆきたいです。

Scalaの非正格関数

JSで死ぬほど出てくる↓の形で表されます。

def hoge(f: () => Int) = ... f()

hoge( () => 21 )

この形式はthunkと呼ばれ、一般に使われています。
jsのライブラリでは、redux-thunkなどでも名前が使われています。

ただ、毎回書くのが面倒なので、Scalaでは最初の空カッコは省略し、さらに呼び出しでもカッコが要らなくなります。
あら便利。

def hoge(f: => Int) = ... f

サンクから値を取り出す際、結果をキャッシュはしてくれないので、lazy付きの定数に放り込んであげる必要があります。

lazy val x = f

こうすると、xが初めて使われる際にfが評価され、さらに結果をキャッシュしてくれます。

Stream

ストリームの実装、キャッシュをするためのスマートコンストラクタが紹介された後、いつもの練習問題です。

StreamのtoListを作れ。

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

とりあえずこれで動きますが、末尾再帰でないので遅いです。
解答ではreverse付きのtailrec、mutable.ListBufferを使った答えも挙げられていました。

take, drop、takeWhileを作れ。

  def take(n: Int): Stream[A] =
    this match {
      case Cons(h, t) if n > 0 => cons(h(), t().take(n - 1))
      case _ => Empty
    }

  def drop(n: Int): Stream[A] =
    this match {
      case Cons(h, t) if n > 0 => t().drop(n - 1)
      case _ => this
    }

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

takeの解答ですが、n==1の時に余計なt()が呼び出されるのが無駄なので、n==1の時は分岐していました。
細かい所ですが、多くの箇所で使われるとなると、細やかな所に気を使わないといけないですね。

次に、existsの実装を通してStreamを活用する場面が書かれています。
見つかった時点で打ち切ることができ、foldRightもそのように実装することで最後まで評価をしなくて済みます。

ここでまたまた練習問題。

全て条件にマッチするかを判定するforAllを実装せよ。

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

なんと全くStreamを意識せず書くことが出来ました。
まさに一般化されていますね。

foldRightを使ってtakeWhileを実装せよ。

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

foldRightを使ってheadOptionを実装せよ。

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

リストが空であればNoneなので、非常に素直な実装のこれだけで十分です。
2つ目の引数（b）が評価されていないので、先頭要素以降はループが発生せずちゃんとStreamを活かせています。

foldRightを使ってmap / filter / append / flatMap を実装せよ。

答え合わせで気づきましたが、Emptyの型指定はこのような形でも行えるようです。
楽ちん。

  def map[B](f: A => B): Stream[B] =
    foldRight(Empty: Stream[B])((a,b) => cons(f(a), b))

  def filter(f: A => Boolean): Stream[A] =
    foldRight(Empty: Stream[A])((a,b) => if(f(a)) cons(a, b) else b)

意気揚々と書いていると、appendでコンパイルエラーが取れません。
covarient / contravariant 辺りの問題ですが、いまいち分かっていなかったため他サイトのお世話になりました。

とてもわかりやすいです。
パッと使いこなせるかどうかはかなり怪しいですが、とりあえずvariance checkを回避できました。

  def append[B>:A](a: => Stream[B]): Stream[B] =
    foldRight(a)((c,d) => cons(c, d))

  def flatMap[B>:A](s: A => Stream[B]): Stream[B] =
    foldRight(Empty: Stream[B])((a,b) => s(a).append(b))

これらの関数を使ってStreamを処理すると、必要な部分だけ評価しており、余計なインスタンスが生成されることがありません。
下記のような処理をしても、とても効率よく処理してくれて重いリストも安心です。

st.map(---).filter(---)
st.filter(---).headOption

不完全なインスタンス化で処理を進行するため、ループの適用順自体が変わっているように見えます。
そのため、ストリームは「ファーストクラスループ」と呼ばれることもあるそうです。

filterで捨てられる、mapで生まれた要素もすぐGCの処理対象になるため、メモリにも優しいです。
また、より効率の良いストリーム計算については先の章で触れるそうです。

さて、ストリームの基礎を抑えたところで、よく例に挙げられる無限ストリームに触れています。
一瞬触れたら早速練習問題です。

指定された値の無限ストリームを生成する関数constantを作れ。

def constant[A](a: A): Stream[A] = cons(a, constant(a))

と簡単に書けるのですが、毎回consをするので少しもったいないです。
より良い方法として、lazyなオブジェクトを作って使い回す方法が挙げられています。

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

n, n+1, n+2...の無限ストリームを作る関数fromを作れ。

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

フィボナッチ数列ストリームを作る関数fibsを作れ。

  def fibs(): Stream[Int] = {
    def loop(i1: Int, i2: Int): Stream[Int] = cons(i2, loop(i1 + i2, i1))
    loop(1, 0)
  }

よくある例ですね。

より汎用的なストリーム生成関数unfoldを作れ。また、それを使ってfibs / from / constant / onesを作れ。

  def u_fibs(): Stream[Int] =
    unfold((0, 1))(a => Some(a._1, (a._2, a._1 + a._2)))
  def u_fibs2(): Stream[Int] =
    unfold((0, 1))(a => {
      a match {
        case (i1, i2) => Some(i1, (i2, i1 + i2))
      }
    })
  def u_fibs3(): Stream[Int] =
    unfold((0, 1)) { case (i1, i2) => Some(i1, (i2, i1 + i2)) }

  def u_from(n: Int): Stream[Int] =
    unfold(n)(s => Some(s, s + 1))

  def u_constant(n: Int): Stream[Int] =
    unfold(n)(s => Some(s, s))

  def u_ones: Stream[Int] =
    unfold(1)(s => Some(s, s))

fibsは3つありますが、どれも同じです。
変数分離時にmatchを省略して書く書き方を使うと、とても楽です。

unfoldを使ってmap / take / takeWhile / zipWith / zipAllを作れ。

  def u_take(n: Int): Stream[A] =
    unfold((this, n)) {
      case (Cons(h, t), i) if i > 0 => Some(h(), (t(), i-1))
      case _ => None
    }
  def u_takeWhile(f: A => Boolean): Stream[A] =
    unfold(this) {
      case Cons(h, t) if f(h()) => Some(h(), t())
      case _ => None
    }
  def zipWith[B, C](l2: Stream[B])(f: (A, B) => C): Stream[C] = {
    unfold((this, l2)) {
      case (Cons(h1, t1), Cons(h2, t2)) => Some(f(h1(), h2()), (t1(), t2()))
      case _ => None
    }
  }
  //  def zipAll[B, C>:A](l2: Stream[B])(v1: A, v2: B): Stream[(A,B)] = {
  //    unfold((this, l2)) {
  //      case (Empty, Cons(h2, t2)) => Some((v1, h2()), (Empty, t2()))
  //      case (Cons(h1, t1), Empty) => Some((h1(),v2), (t1(), Empty))
  //      case (Cons(h1, t1), Cons(h2, t2)) => Some((h1(), h2()) -> (t1(), t2()))
  //      case _ => None}
  //  }
  def zipAll[B](l2: Stream[B]): Stream[(Option[A], Option[B])] = {
    unfold((this, l2)) {
      case (Empty, Cons(h2, t2)) => Some((None, Some(h2())), (Empty, t2()))
      case (Cons(h1, t1), Empty) => Some((Some(h1()), None), (t1(), Empty))
      case (Cons(h1, t1), Cons(h2, t2)) => Some((Some(h1()), Some(h2())), (t1(), t2()))
      case _ => None
    }
  }

解答を見るとzipAllで(Option[A], Option[B])を返していますが、Noneにしろと指定されているので従います。

startWithを作れ。

  def startsWith[B](s: Stream[B]): Boolean =
    zipAll(s).takeWhile(_._2.isDefined).forAll({
        case (Some(a), Some(b)) => a == b
        case _ => false
    })

2つのストリームをペアにしてから、プレフィックス分だけ取り出し、全ての要素が一致するかを判定しました。

unfoldを使ってtailsを実装せよ。

普通のtailのように、ちょっとずつ削っていけば良さそうです。
空ストリームは明示的にくっつけてあげないといけません。

  def tails: Stream[Stream[A]] =
    unfold(this) {
      case Empty => None
      case s => Some(s, s.drop(1))
    }.append(Stream(empty))

tailsを一般化してscanRight関数を作れ。

分からないので解答を確認。
メモとしての変数をくっつけてfoldRightで生成しているようです。
tailsはunfoldを使って書いたのに、一般化したこちらではunfoldが使えないというのが何だか不思議です。
やってることは同じに見えるのですが……。

思ったこと

なんとか終わりました。
軽そうに見えて重たい商です。
使いこなす所まで至るにはまだまだ修行が必要そうですが、知ってるか知らないかでは応用範囲が大きく変わってきそうです。
効率的な処理を行う上では必須ですし、記述と評価を切り離すことでモジュール性も上がると述べられています。
後の章でも例が沢山出てくるらしく、まだまだ奥が深そうだ……。

次の章では「状態をいかに扱うか」という点に触れます。

続き:

Scala関数型デザイン&プログラミング 〜5章 (5)

Scala関数型デザイン&プログラミング〜5章 (5)