Functional Programing in Scala 読書録

イントロダクション

研究室で開かれた Functional Programing in Scala の勉強会に参加したときの記録です。

基本的には例題・演習に対してのメモばかり書き留めていきます。

第６章

nextInt

考察

nextIntは以下のように実装されています。

	trait RNG {
	  def nextInt: (Int, RNG) 
	}
	
	object RNG {
	  case class Simple(seed: Long) extends RNG {
	    def nextInt: (Int, RNG) = {
	      val newSeed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL 
	      val nextRNG = Simple(newSeed) 
	      val n = (newSeed >>> 16).toInt 
	      (n, nextRNG) 
	    }
	  }
	}

クラスSimpleの関数であるnextIntは、引数を持ちません。

代わりにクラスSimpleが初期化されたときに要する引数seedを用いて乱数を生成します。

返り値は乱数と自身が所属するクラスSimpleのタプルであり、

新たに作成したクラスSimpleがそのメンバであるnextIntを呼ぶことで、次の乱数が生成されます。

（ちなみに、解答ではSimpleクラスとなっていますが、テキストではSimpleRNGクラスと書かれています。）

使用例

	scala> import fpinscala.state._
	import fpinscala.state._
	
	scala> val s0 = RNG.Simple(1)
	s0: fpinscala.state.RNG.Simple = Simple(1)
	
	scala> val s1 = s0.nextInt
	s1: (Int, fpinscala.state.RNG) = (384748,Simple(25214903928))
	
	scala> val s2 = s1._2.nextInt
	s2: (Int, fpinscala.state.RNG) = (-1151252339,Simple(206026503483683))
	
	scala> val s3 = s2._2.nextInt
	s3: (Int, fpinscala.state.RNG) = (-549383847,Simple(245470556921330))
	
	scala> val s4 = s3._2.nextInt
	s4: (Int, fpinscala.state.RNG) = (1612966641,Simple(105707381795861))

nonNegativeInt

考察

nonNegativeIntは以下のように実装されています。

	def nonNegativeInt(rng: RNG): (Int, RNG) = {
	  val (i, r) = rng.netInt
	  (if (i < 0) -(i + 1) else i, r)
	}

nonNegativeIntはRNG型の変数rngを引数に取り、Int型とRNG型のタプルを返します。

まずrngを用いてnextIntを行い（整数, 次の状態）のタプルを得ます。

得た整数が負の数なら1を足して符号を反転し、正の数ならばそのままにします。

（１足すのはおそらく、２の補数の関係だと思います。）

そうして得られた（0以上の整数, 次の状態）というタプルがdoubleの返り値です。

使用例

	scala> import fpinscala.state._
	import fpinscala.state._
	
	scala> val s = RNG.Simple(1)
	s: fpinscala.state.RNG.Simple = Simple(1)
	
	scala> val (a1, rng1) = s.nextInt
	a1: Int = 384748
	rng1: fpinscala.state.RNG = Simple(25214903928)

double

考察

doubleは以下のように実装されています。

	def double[A,B](rng: RNG): (Double, RNG) = {
	  val (i, r) = nonNegativeInt(rng)
	  (i / (Int.MaxValue.toDouble + 1), r)
	}

doubleはRNG型の変数rngを引数に取り、Double型とRNG型のタプルを返します。

まずrngを引数にnonNegativeIntを行い（0以上の整数, 次の状態）のタプルを得ます。

得た整数をInt型の最大値で割ることで、整数は1未満の数になります。

そうして得られた（0以上1未満の浮動小数点数, 次の状態）というタプルがdoubleの返り値です。

使用例

	scala> import fpinscala.state._
	import fpinscala.state._
	
	scala> val s = RNG.Simple(1)
	s: fpinscala.state.RNG.Simple = Simple(1)
	
	scala> val (a1, rng1) = s.nextInt
	a1: Int = 384748
	rng1: fpinscala.state.RNG = Simple(25214903928)
	
	scala> RNG.double(rng1)
	res0: (Double, fpinscala.state.RNG) = (0.5360936457291245,Simple(206026503483683))

map

考察

mapは以下のように実装されています。

	def map[A,B](s: Rand[A])(f: A => B): Rand[B] =
	  rng => {
	    val (a, rng2) = s(rng)
	    (f(a), rng2)
	  }

mapの定義は関数になっています。その処理を追っていきましょう。

rngを引数に指定する。
rngを引数としてs関数を実行する。その結果を（a, rng2）に代入する。
aを引数としてf関数を実行する。
その結果とrng2のタプル（f(a), rng2）を返り値とする。

以上の手順を踏んだ関数が、mapの定義です。

map自体の返り値はタプル(f(a), rng2)ではなく、関数rng => (f(a), rng2))であることに注意してください。

（そもそも、Rand[B]自体がRNG => (B, RNG)という関数型なのです。）

mapを単独で用いた場合は関数が返ってきます。

mapの結果として得られた関数は、引数にRNG型を指定することで機能します。使用例をご覧ください。

使用例

	scala> import fpinscala.state._
	import fpinscala.state._
	
	scala> val rng = RNG.Simple(1)
	rng: fpinscala.state.RNG.Simple = Simple(1)
	
	scala> val (d1, rng2) = RNG._double(rng)
	d1: Double = 1.7916224896907806E-4
	rng2: fpinscala.state.RNG = Simple(25214903928)
	
	scala> val u = RNG.unit(10)
	u: fpinscala.state.RNG.Rand[Int] = <function1>
	
	scala> val m = RNG.map(u(_))(_+1)
	m: fpinscala.state.RNG.Rand[Int] = <function1>
	
	scala> m(rng2)
	res0: (Int, fpinscala.state.RNG) = (11,Simple(25214903928))

map2

考察

map2は以下のように実装されています。

	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はふたつのグループの引数を持ちます。

第一グループには二種類のRand[?]型の値ra、rbを取り、

第二グループには「Rand型を構成する２つの型を受け取って新たな型を返す関数f」を取ります。

そして返り値はfがもたらす新たな型CをRandにしたものを返します。

Rand[?]型は関数ですので「引数rngを受け取ってタプル（f(a, b), r2）を返す」関数が map2の実装となります。

使用例

	scala> import fpinscala.state._
	import fpinscala.state._

	scala> val s = RNG.Simple(1)
	s: fpinscala.state.RNG.Simple = Simple(1)

	scala> val (a1, rng1) = s.nextInt
	a1: Int = 384748
	rng1: fpinscala.state.RNG = Simple(25214903928)

	scala> val (a2, rng2) = RNG.nonNegativeInt(rng1)
	a2: Int = 1151252338
	rng2: fpinscala.state.RNG = Simple(206026503483683)

	scala> val (a3, rng3) = RNG.double(rng2)
	a3: Double = 0.2558267889544368
	rng3: fpinscala.state.RNG = Simple(245470556921330)

	scala> val f = RNG.map2(RNG.nonNegativeInt, RNG.double)(_ + _)
	f: fpinscala.state.RNG.Rand[Double] = <function1>

	scala> f(rng1)
	res0: (Double, fpinscala.state.RNG) = (1.1512523382558267E9,Simple(245470556921330))

flatMap

考察

flatMapは以下のように実装されています。

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

flatmapが行う処理は、Mapとほとんど変わりません。

mapとの違いは偏にシグネチャにあります。

ここでmapのシグネチャと実装を見てみましょう。

	def map[A,B](s: Rand[A])(f: A => B): Rand[B] =
	  rng => {
	    val (a, rng2) = s(rng)
	    (f(a), rng2)
	  }

mapの第二引数では「A型を引数に取りB型を返す関数」をとっていましたが、

flatMapの第二引数gでは「A型を引数に取りRand[B]型（即ち、B型とRNGのタプル）を返す関数」を取っています。

gの処理を展開すると、「A => RNG => (B, RNG)」となります。

gではふたつの関数が処理されます。

まずはAを引数に取ってRNGを返す関数の処理が行われ、

次にその結果を引数に取って、タプル（B, RNG）を返す処理が実行されます。

そのためgを呼び出す際にはカリー化を行い、関数の入れ子構造をg(a)(r1)と簡潔にまとめています。

カリー化部分について説明します。

ここではまずg(a)という関数を呼びます。そして返り値の関数の引数にRNG型のr1を指定します。

g(a)にnonNegativeIntのようなrngを必要とする関数を置くことができるという訳です。

もう少し具体的に言うならば、シグネチャに引数aを取りながら定義で「rng => {...}」という形を持つタイプの関数をg(a)に置けます。

使用例

	scala> import fpinscala.state._
	import fpinscala.state._

	scala> val s = RNG.Simple(1)
	s: fpinscala.state.RNG.Simple = Simple(1)

	scala> val (a1, rng1) = s.nextInt
	a1: Int = 384748
	rng1: fpinscala.state.RNG = Simple(25214903928)

	scala> def g(a: Int): RNG.Rand[Double] = rng => {
     | val (b, rng2) = RNG.double(rng)
     | (a.toDouble+b, rng2)}
	g: (a: Int)fpinscala.state.RNG.Rand[Double]

	scala> val fm = RNG.flatMap(RNG.nonNegativeInt)(g)
	fm: fpinscala.state.RNG.Rand[Double] = <function1>

	scala> fm(rng1)
	res6: (Double, fpinscala.state.RNG) = (1.1512523382558267E9,Simple(245470556921330))

flatMapによるmapの実装

flatMapを使えばmapを再現できます。（引数、返り値もmapのままです。）

以下にその実装を示します。

	def _map[A,B](s: Rand[A])(f: A => B): Rand[B] =
	  flatMap(s)(a => unit(f(a)))

mapとflatMapの違いは引数の第二グループにあったので、今回もそこに着目します。

flatMapの第二引数は以下の手順を踏んだ処理を持つ関数となっています。

引数aを取る。
aを引数にしてfを実行する。
f(a)の結果を引数にしてunitに渡す。
unitは引数aを受け取って関数Randを返す。

以上でa => Randの構図が成立して、flatMapの第二引数の条件が満たされました。

「aを引数に取ってRandを返す関数」を指定しているだけです。

少々複雑ですが、関数を代入するという高階関数の概念が分かっていれば理解できるかと思います。

現在状態を変えずに、形だけ状態遷移を行う関数unitを活用することで、 flatMapでmapを実装することができます。

flatMapによるmap2の実装

map2についても、flatMapによって実装することができます。

実装は以下の通りです。

	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)))

flatMapの第一引数の処理でraから乱数を生成し、

第二引数の処理でrbから乱数を生成して関数fを実行しています。

flatMapの第二引数とカリー化部分の解説をすると、

flatMapの第二引数gにa => map(rb)(b => f(a, b)))を取る。
gはaを引数に取り、mapを呼び出す。
mapの中ではまずrbから（乱数, 次の状態）が生成される。
mapの第二引数は引数bを要求し、f(a, b)を返す。
mapの実装を見ると、bはmapの第二引数の引数なので、rbの乱数が指定される。
flatMapの実装よりaはraの乱数なので、f(raの乱数, rbの乱数)が実行される。
最終的にmapは（fの結果, rbの次の状態）を返す。
mapは関数Randを返すので、その関数がg(a)の結果となる。
g(a)の結果である関数を、引数r1で実行する。
Randを返してflatMapが終了する。
すべての処理が終わったので、Randを返してmap2が終了する。

flatMapの第二引数の引数aに、第一引数が生成した乱数が入ることがポイントです。

また高階関数は引数と返り値を指定するものだと解釈しておけば理解しやすいかと思います。

三谷研 最果ての地