Scala関数型デザイン&プログラミング 〜6章 (6)
"Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド"を買いました。
ちょっとずつ読んで、各章の内容をまとめてゆきます。
今回は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が終わり、次回からより本質的な話になっていくようです。
がんばります。
この章は消化不良なので、しばらく読んでからまた振り返りたいと思います。
