Scala関数型デザイン&プログラミング 〜6章 (6)

2016-11-20

“Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド"を買いました。 ちょっとずつ読んで、各章の内容をまとめてゆきます。

https://www.amazon.co.jp/exec/obidos/asin/4844337769/esplo06-22

今回は6章。関数型で、如何に状態を扱うか？という話です。 今回で遂にPart1がおしまいです。

前回 https://blog.esplo.net/entry/2016/10/sfdp-5

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が終わり、次回からより本質的な話になっていくようです。 がんばります。

この章は消化不良なので、しばらく読んでからまた振り返りたいと思います。

development

「Team Geek」 感想

「Soft Skills」 感想

comments powered by Disqus