“Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド"を買いました。 ちょっとずつ読んで、各章の内容をまとめてゆきます。
https://www.amazon.co.jp/exec/obidos/asin/4844337769/esplo06-22
今回は5章。遅延評価のところです。
https://blog.esplo.net/entry/2016/09/sfdp-4
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 辺りの問題ですが、いまいち分かっていなかったため他サイトのお世話になりました。
http://tkawachi.github.io/blog/2013/10/09/covariant-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が使えないというのが何だか不思議です。 やってることは同じに見えるのですが……。
思ったこと
なんとか終わりました。 軽そうに見えて重たい商です。 使いこなす所まで至るにはまだまだ修行が必要そうですが、知ってるか知らないかでは応用範囲が大きく変わってきそうです。 効率的な処理を行う上では必須ですし、記述と評価を切り離すことでモジュール性も上がると述べられています。 後の章でも例が沢山出てくるらしく、まだまだ奥が深そうだ……。
次の章では「状態をいかに扱うか」という点に触れます。