Scala関数型デザイン&プログラミング 〜5章 (5)
"Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド"を買いました。 ちょっとずつ読んで、各章の内容をまとめてゆきます。
Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド (impress top gear)
- 作者: Paul Chiusano,Rúnar Bjarnason,株式会社クイープ
- 出版社/メーカー: インプレス
- 発売日: 2015/03/20
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (7件) を見る
今回は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が使えないというのが何だか不思議です。 やってることは同じに見えるのですが……。
思ったこと
なんとか終わりました。 軽そうに見えて重たい商です。 使いこなす所まで至るにはまだまだ修行が必要そうですが、知ってるか知らないかでは応用範囲が大きく変わってきそうです。 効率的な処理を行う上では必須ですし、記述と評価を切り離すことでモジュール性も上がると述べられています。 後の章でも例が沢山出てくるらしく、まだまだ奥が深そうだ……。
次の章では「状態をいかに扱うか」という点に触れます。