2016-01-16 第１２回 関数型プログラミング勉強会（Scala）の振り返り

Scala関数型デザイン&プログラミング―Scalazコントリビューターによる関数型徹底ガイド

第６章 純粋関数型の状態

前回の続きより

状態の処理に適したAPI

• RNG => (A, RNG) のように RNGの状態から別のRNGの状態を返すような関数を「状態アクション」または「状態遷移」と呼ばれる。
• コンビネータ ＝ ここでは状態アクションを行うための高階関数

Randの定義：

type Rand[+A] = RNG => (A, RNG)

Exercise 6.5

GitHubにあがってる解答で問題なし。 mapを使ったものとそうで無いものの実装を比較してみる

mapを使ってる場合

val _double: Rand[Double] =
  map(nonNegativeInt)(_ / (Int.MaxValue.toDouble + 1))

mapを使ってない場合

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

mapではnonNegativeIntが返すタプルの最初の要素に割り算を行った結果をもつタプルのリストを作っている

Exercise 6.6

GitHubにあがってる解答で問題なし。

解答のコメントには呼び出し元のRNGを第１引数のRandに渡し、そこで生成されたRNGを第２引数のRandに渡すように書いてある。 そうしないと第１引数にも第２引数にも同じRNGが渡され、両方で生成される結果が同じになるため期待した値にはならなない。

解答より：

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

なぜ２つのRandの引数部分と関数の引数部分が分かれているかの疑問があがった
→ ２つのRandを受け取ることと関数で処理をすることとでは性質が違うためかと思われる。

ここでカリー化の話も出てきた

def map2[A,B,C](ra: Rand[A], rb: Rand[B])(f: (A, B) => C)

と

def map2[A,B,C](ra: Rand[A])(rb: Rand[B])(f: (A, B) => C)

と

def map2[A,B,C](ra: Rand[A], rb: Rand[B], f: (A, B) => C)

は同じ

Exercise 6.7

GitHubにあがってる解答で問題なし。

パターンマッチを使うパターンで解答している参加者もいた。

def sequence0[A](fs: List[Rand[A]]): Rand[List(A)] = {
  rng: RNG => {
    fs match {
      case Nil => (Nil, rng) // unit(Nil:List[A])
      case h :: t => {
        val (hd, nextRng) = h(rng)
        val (tl, nextRng2) = sequence0(t)(nextRng)
        (hd :: tl, nextRng2)
      }
    }
  }
 }

::の話題も出たのでリストのおさらい。

• 要素 :: リストで最初に要素を持ち、後ろにリストを持つ新しいリストができる
• リストの最後はNil（空のList）

map2(r, acc)(_ :: _)

は

map2(r, acc)( (r1, acc1) => r1::acc1)

と同じ

入れ子の状態アクション

Exercise 6.8

GitHubにあがってる解答で問題なし。

Exercise 6.9

GitHubにあがってる解答で問題なし。

状態アクションデータ型の一般化

• RandのメソッドはRNGに特定されているが汎用的にすることも可能
• Rand型より汎用的なState型を作成

type Rand[+A] = RNG => (A, RNG)

↓

type State[S, +A] = S => (A, S)

こうすることでRandをStateを使って表すことも可能

Exercise 6.10

解答ではsequenceをfoldRightと再帰とfoldLeftを使ったパターンを示している。

再帰の例のコメント

This implementation uses a loop internally and is the same recursion pattern as a left fold. It is quite common with left folds to build up a list in reverse order, then reverse it at the end. (We could also use a collection.mutable.ListBuffer internally.)

この実装はループを内部で使い、左のfoldと同じ 再帰パターンにしている。 左のfoldを逆の順にしてリストを構築し最後に 再度逆順にするのはよくあることだ。 （内部でListBufferを使うことも可能）

foldLeftの例のコメント

We can also write the loop using a left fold. This is tail recursive like the previous solution, but it reverses the list before folding it instead of after. You might think that this is slower than the foldRight solution since it walks over the list twice, but it's actually faster! The foldRight solution technically has to also walk the list twice, since it has to unravel the call stack, not being tail recursive. And the call stack will be as tall as the list is long.

左のfoldを使ったループで書くことも可能。 これは前の解決の末尾再帰のようなものだが foldする後ではなく前にリストを逆順にしている。 リストを２度たどるのでfoldRightより遅いと 思うかもしれないが、実際は早い。 foldRightもまた末尾再帰ではないので コールスタックをほどく必要があるので 技術的に２回リストをたどっている。 そしてリストが長いほどコールスタックも高く積まれる。