新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。もう新人じゃないかも…

学習記録:Scala関数型デザイン 第6章

第6章:純粋関数型の状態(続き)

状態の処理に適したAPI(続き)

状態アクションの結合

先ほど定義したmapは,殘念ながらintDoubleやdoubleIntを実装できるほど高性能ではない。
そこで,新しいコンビネータmap2が必要となる。
map2では,単項関数ではなく2項関数を使って2つのRNGアクションを1つにまとめることができる。

Exercise 6.6
  • raとrbの2つのアクションをまとめるmap2を実装せよ。

raとrbを使ってa, b二つの値を取得し,最終的にfを使ってcにまとめる。

  def map2[A,B,C](ra: Rand[A], rb: Rand[B])(f: (A, B) => C): Rand[C] =	
    rng	=> {
      val (a, r1) = ra(rng)
      val (b, r2) = rb(r1)
      (f(a,b), r2)
    } 

map2コンビネータにより,任意のRNG状態アクションの結合を記述することができる。
A型の値を生成するアクションと,B型の値を生成するアクションがある場合,それらを組み合わせて1つのアクションにまとめられる。

  def both[A,B](ra: Rand[A], rb: Rand[B]): Rand[(A,B)] =
    map2(ra, rb)((_, _))

これを使ってintDoubleとdoubleIntを以下のように簡潔に書き直せる。

val randIntDouble: Rand[(Int, Double)] = both(int, double)
val randDoubleInt: Rand[(Double, Int)] = both(double, int)
入れ子の状態アクション

ここまで,RNG値を明記したり渡したりしない実装に向かって進んできている。
mapとmap2コンビネータを利用することで,書くのが面倒な上に書き間違いをしやすい関数を簡潔に実装することができた。
しかし,mapとmap2を使ってもうまく記述できない関数が幾つか存在する。

nonNegativeLessThanはそうした関数の1つで,[0, n)の整数を生成する。
実装上の最初の課題は,nを法とする自然数を生成することになるかもしれない。

def nonNegativeLessThan(n: Int): Rand[Int] =
  map(nonNegativeInt) { _ % n }

このようにすれば,確かに範囲内の数は生成されるが,Intの最大値に起因する歪みが発生してしまう。
つまり,Int.MaxValueがnで割り切れない場合,(Int.MaxValue % n)よりも小さい数が出現する頻度が高くなってしまう。
そこで,nonNegativeIntが生成した数が,「32bit整数に収まりかつnの最大の倍数」よりも大きい数である場合,
より小さい数を得られることを期待したジェネレータをリトライする。

def nonNegativeLessThan(n: Int): Rand[Int] =
  map(nonNegativeInt) { i =>
    val mod = i % n
    if (i + (n - 1) - mod >= 0) mod   // modじゃなく,(mod, rng)を返さないといけない
    else nonNegativeLessThan(n)(???)
  }

しかし,これではRand[Int],つまり整数とRNGを返すはずが,整数しか返さない関数になってしまっている。
これはmapによってrngが明示的に渡さなくなってしまったことに起因するものなので,mapを使用せずに明示的に渡す必要がある。

def nonNegativeLessThan(n: Int): Rand[Int] =
  { rng =>
    val (i, rng2) = nonNegativeInt(rng)
    val mod = i % n
    if (i + (n - 1) - mod >= 0) (mod, rng2)
    else nonNegativeLessThan(n)(rng)
  }

このような受け渡しを自動で行うコンビネータがあれば便利だが,mapやmap2はその期待に応えてくれない。
これには,より強力なコンビネータflatMapが必要となる。

Exercise 6.8
  • flatMapを実装し,それを使ってnonNegativeLessThanを実装せよ。

mapのようにA => Bの関数ではなく,A => Rand[B]の関数を引数とする。

  def flatMap[A,B](f: Rand[A])(g: A => Rand[B]): Rand[B] =
    rng => {
      val (a, r1) = f(rng)
      g(a)(r1)
    }

Rand[Int]を返すため,modではなくunit(mod)を返す。

  def nonNegativeLessThan(n: Int): Rand[Int] =
    flatMap(nonNegativeInt) { i =>
      val mod = i % n
      if (i + (n - 1) - mod >= 0) unit(mod)
      else nonNegativeLessThan(n)
    }
Exercise 6.9
  • flatMapを使ってmapとmap2を再実装せよ。
  def mapViaFlatMap[A,B](s: Rand[A])(f: A => B): Rand[B] =
    flatMap(s)(a => unit(f(a)))

  def map2ViaFlatMap[A,B,C](ra: Rand[A], rb: Rand[B])(f: (A, B) => C): Rand[C] =
    flatMap(ra)(a => map(rb)(b => f(a, b)))

本章の冒頭で示したサイコロを振る例について改めて考えてみる。
nonNegativeLessThanを使ったrollDieの実装は以下のようになる。

def rollDie: Rand[Int] = nonNegativeLessThan(6)

上記の関数には,「1つ違い」のエラーが含まれている。
つまり,上記の関数は1〜6ではなく,0〜5の値を返してしまう。
この関数をさまざまなRNG状態でテストすれば,0を返すようなRNGがすぐに見つかるはずである。

scala> RNG.rollDie(RNG.SimpleRNG(6))._1
res13: Int = 5

scala> RNG.rollDie(RNG.SimpleRNG(5))._1
res14: Int = 0

同じ乱数ジェネレータSimpleRNG(5)を使えば,この現象を正確に再現することができる。
また,このバグの修正も簡単である。

def rollDie: Rand[Int] = map(nonNegativeLessThan(6))(_ + 1)

これでrollDieが1〜6の値を返すようになった。

scala> RNG.rollDie(RNG.SimpleRNG(6))._1
res18: Int = 6

scala> RNG.rollDie(RNG.SimpleRNG(5))._1
res19: Int = 1