Scala関数型デザイン&プログラミング 〜6章 (6)
"Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド"を買いました。 ちょっとずつ読んで、各章の内容をまとめてゆきます。
Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド (impress top gear)
- 作者: Paul Chiusano,Rúnar Bjarnason,株式会社クイープ
- 出版社/メーカー: インプレス
- 発売日: 2015/03/20
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (7件) を見る
今回は6章。関数型で、如何に状態を扱うか?という話です。 今回で遂にPart1がおしまいです。
6章
この章では、状態を扱う方法が説明されています。 純粋関数なのにどうやって??という疑問がまず浮かびますが、やることは同じです。 リストでは結果を格納するためのリストを引数に入れていました。 状態を遷移させたければ、引数に状態を渡して、また返してあげれば大丈夫そうです。 ここでは乱数を生成する関数を例にとっています。
恒例の早速練習問題。
nextIntを使って、非負整数を返す関数を作れ。なお、nextIntがInt.MinValueを返すと対応する値がないので、特殊ケースとして対応すること。
負の場合は+1してあげることで、[0, Int.MaxValue]の全てが2回登場するようにできます。
def nonNegativeInt(rng: RNG): (Int, RNG) = { val (i, next) = rng.nextInt if(i < 0) (-(i + 1), next) else (i, next) }
[0, 1)のDouble値を返す関数を作れ。
def double(rng: RNG): (Double, RNG) = { val (i, next) = nonNegativeInt(rng) (i.toDouble / (Int.MaxValue.toDouble +1), next) }
様々な型を持ったタプルを作る関数を作れ。
def intDouble(rng: RNG): ((Int,Double), RNG) = { val (i1, r1) = rng.nextInt val (d2, r2) = double(r1) ((i1, d2), r2) } def doubleInt(rng: RNG): ((Double,Int), RNG) = { val ((i1, d1), next) = intDouble(rng) ((d1, i1), next) } def double3(rng: RNG): ((Double,Double,Double), RNG) = { val (d1, r1) = double(rng) val (d2, r2) = double(r1) val (d3, r3) = double(r2) ((d1, d2, d3), r3) }
沢山書くのがめんどくさいな〜と思った時に以下の問題が出てきます。うまい。
ランダムな整数のリストを作成する関数を作れ。
def ints(count: Int)(rng: RNG): (List[Int], RNG) = { @tailrec def loop(n: Int, acc: List[Int], r: RNG): (List[Int], RNG) = { n match { case 0 => (acc, r) case _ => val (i, nr) = r.nextInt loop(n-1, i :: acc, nr) } } loop(count, List.empty[Int], rng) }
ここで、RNGを受け取って値とnextRNGを返す型、Rand[+A]が導入されます。 よく出てくるので、まとめて扱うと便利そうですね。 このRandに対してもmapが定義されますので、これを使って書き換えろという練習問題が出ます。
mapを使ってdoubleをもう少し要領よく実装しなおせ。
なんだか随分曖昧な指示です。
// before def double(rng: RNG): (Double, RNG) = { val (i, next) = nonNegativeInt(rng) (i.toDouble / (Int.MaxValue.toDouble +1), next) } // after def mapDouble: Rand[Double] = map(nonNegativeInt)(_.toDouble / (Int.MaxValue.toDouble +1))
随分すっきりしました。 共通パターンになりそうですね。
と思ったら、すぐさま「mapは高性能ではありません。map2を作りましょう」などと言われて心が折れます。 map2があれば、任意のRNG型アクションの結合ができるようになります。
map2を実装せよ。
def map2[A,B,C](ra: Rand[A], rb: Rand[B])(f: (A, B) => C): Rand[C] = rng => { val (a, rng2) = ra(rng) val (b, rng3) = rb(rng2) (f(a, b), rng3) }
実装自体は簡単です。
[難問] 遷移のlistを1つの遷移にまとめるためのsequenceを実装せよ
_sequenceのように書いていましたが、Randを使ってない……。 解答を見ると、1行で書かれていました。Randがちゃんと使われています。なるほど。 unitも存在を忘れていました。Randの単位元なので確かに使いドコロはここだ……。
def _sequence[A](fs: List[Rand[A]]): Rand[List[A]] = { rng => { fs.foldRight((List.empty[A], rng))((x, acc) => { val (a, r2) = x(acc._2) (a :: acc._1, r2) }) } } def sequence[A](fs: List[Rand[A]]): Rand[List[A]] = fs.foldRight(unit(List[A]()))((x, acc) => map2(x, acc)(_ :: _)) def intsSeq(count: Int): Rand[List[Int]] = sequence(List.fill(count)(int))
どんどんとrngが隠匿されていますね。 map / map2を使ってもうまく隠匿できないケースが紹介され、さらに強力なflatMapを作れという問題が出ます。
flatMapを実装し、nonNeegativeLessThanを実装せよ。
def flatMap[A,B](f: Rand[A])(g: A => Rand[B]): Rand[B] = { rng => { val (a, r) = f(rng) g(a)(r) } } def nonNegativeLessThan(n: Int): Rand[Int] = { flatMap(nonNegativeInt)(i => { val mod = i % n if(i + (n-1) - mod >= 0) unit(mod) else nonNegativeLessThan(n) }) }
受け渡しが自動化されました。 次の問題で、より関係性がわかりやすくなります。
flatMapを使ってmap, map2を再実装せよ。
def map[A,B](s: Rand[A])(f: A => B): Rand[B] = flatMap(s)(i => unit(f(i))) def map2[A,B,C](ra: Rand[A], rb: Rand[B])(f: (A, B) => C): Rand[C] = flatMap(ra)(a => map(rb)(b => f(a, b)))
すっきりしました。
さて、このような状態の受け渡しを一般化すべく、State型が導入されます。 これを使って以下の問題が出されます。
unit, map, map2, flatMap, sequenceを一般化せよ。
一般化するだけ……とはいかず、状態遷移のイメージが難しいため答えをチラ見しながら書きました。
case class State[S,+A](run: S => (A, S)) { def map[B](f: A => B): State[S, B] = flatMap(a => State.unit(f(a))) def map2[B,C](sb: State[S, B])(f: (A, B) => C): State[S, C] = flatMap(a => sb.map(b => f(a,b))) def flatMap[B](f: A => State[S, B]): State[S, B] = State(s => { val (a, s2) = run(s) f(a).run(s2) } ) } object State { type Rand[A] = State[RNG, A] def unit[S,A](a: A): State[S, A] = State(s => (a, s)) def sequence[S,A](fs: List[State[S, A]]): State[S, List[A]] = fs.foldRight(unit[S, List[A]](List()))((x, acc) => x.map2(acc)(_ :: _)) }
この辺りはスラスラ書けるという状態には程遠いため、また振り返ることになりそうです。
今までやってきたことを鑑みると、結局は命令形プログラムと変わりありません。 各処理で状態を変更し、それを次に受け渡しているからですね。 というわけで、最後の問題が放り投げられます。
[難問] 自販機を作れ。
難しかったので答えを見ました。 抽象度が高いですが、まさしく命令形プログラミングを実現しています。 sequenceを使う辺りが解答だと少しややこしかったので、( )を使う記法にしています。 慣れてくるとスペースの方が読みやすいのかもしれません……。
object Candy { def update = (i: Input) => (s: Machine) => (i, s) match { case (_, Machine(_, 0, _)) => s case (Coin, Machine(false, _, _)) => s case (Turn, Machine(true, _, _)) => s case (Coin, Machine(true, candy, coin)) => Machine(false, candy, coin + 1) case (Turn, Machine(false, candy, coin)) => Machine(true, candy - 1, coin) } def simulateMachine(inputs: List[Input]): State[Machine, (Int, Int)] = for { _ <- sequence(inputs.map((i: Input) => modify[Machine](s => update(i)(s)))) s <- get } yield (s.coins, s.candies) }
思ったこと
状態を持たない処理をずっと書いていましたが、遂に状態まで扱えるようになりました。 使いこなせれば、ステートフルな処理をステートレスに書けるという、極めて強力な記述ができそうです。 だんだんと真髄に近づいてきた感があります。
が、この本はまだ1/3程度しか終わっていません。 今回で遂にPart 1が終わり、次回からより本質的な話になっていくようです。 がんばります。
この章は消化不良なので、しばらく読んでからまた振り返りたいと思います。