by shigemk2

当面は技術的なことしか書かない

予習メモ #functional_shibuya

勉強会 Scala

次回(6/16予定)に向けた予習メモ。随時更新。

5.2　遅延リストの例

  • 遅延性=正格性で、引数の評価をしなくていい選択が出来ること
  • 遅延リスト(ストリーム)
case object Empty extends Stream[Nothing]
case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]

object Stream {
  def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = {
    lazy val head = hd
    lazy val tail = tl
    Cons(() => head, () => tail)
  }

  def empty[A]: Stream[A] = Empty

  def apply[A](as: A*): Stream[A] =
    if (as.isEmpty) empty
    else cons(as.head, apply(as.tail: _*))
}
  • Stream型はList型とよく似ていますが、Consデータコンストラクタは通常の正格値はなく明示的なサンクを受け取る。

5.2.1 ストリームを記憶し、再計算を回避する

  • スマートコンストラクタ（スマート構築子）とは、追加の不変条件を満たすデータ型、あるいはパターンマッチングに使用される「本物」のコンストラクタとはシグネチャが少し異なるデータ型を生成する関数
  • consの引数が Scala によってサンクにまとめられるため、Streamが強制的に評価 されるまでas.head式とapply(as.tail: _*)式は評価されません

5.2.2 ストリームを検査するためのヘルパー関数

Streamのメソッドを実装する練習問題

  • toList
  • drop
  • takeWhile

5.3 プログラムの記述と評価の切り分け

  • 関数型プログラミングの主なテーマの 1 つは関心の分離
  • Stream では、一連の要素を生成するための処理を組み立てることが可能であり、そうした処理のステップはそれらの要素が実際に必要になるまで実行されない

  • 遅延を利用することで、式の記述をその式の評価から切り離すことが可能

  • 実行方法がよくわからない。

def foldRight[B](z: => B)(f: (A, => B) => B): B =   1
  this match {
    case Cons(h,t) => f(h(), t().foldRight(z)(f))   2
    case _ => z
  }
  • 中間ストリームがインスタンス化されないため、ストリームが必要以上に処理されることを心配せずに、既存のコンビネータを新しい方法で簡単に再利用できる
  • 中間ストリームが生成されないため、ストリームの変換に対しては、現在の要素を格納して変換するのに必要な作業メモリだけで十分
  • メモリをすみやかに回収しうる

5.4　無限ストリームと余再帰

  • 無限のストリーム

f:id:shigemk2:20150607161950p:plain

  • 再帰関数が再帰処理によって入力を小さくしていくことで終了するのに対し、余再帰関数は生産性が続く限り終了する必要がない
  • つまり、限られた時間の中で評価できる結果が常に増えていく

5.5 まとめ

  • 非正格性は関数型コードを記述するときに効率性を回復させるための手法
  • 非正格性は、式の記述をその評価の方法やタイミングから切り離すことで、モジュール性を向上させることが目的
  • 同じ記述を複数のコンテキストで再利用
  • 次は状態に対する純粋関数型のアプローチ

6 純粋関数型の状態

  • 乱数の生成を例に用いて、状態を操作する純粋関数型のプログラムを記述する方法
  • ここでの目標は、ステートフル API を純粋関数型にするための基本的なパターンを示す

6.1 副作用を使った乱数の生成

  • 状態の更新は副作用として実行されるため、乱数メソッドは参照透過ではない。

  • そのことはテスト、合成、並列化が容易ではなく、モジュール性に乏しいことを意味する

  • バギーなメソッドの例

def rollDie: Int = {
  val rng = new scala.util.Random
  rng.nextInt(6)
  // 0 ~ 5 の乱数を返す
}
  • 1-6を返すのが期待されるのに0-5が帰るのは明らかにバグであるし、この場合はどこがバグの原因なのか特定するのも容易であるが、問題はそこではなく、参照透過ではない関数の場合、どこがバグっているのかメソッドが複雑になるにつれわからなくなる

6.2 純粋関数型の乱数の生成

  • 生成された乱数だけを返し、内部状態がそこで変化して更新されるままにするのではなく、乱数と新しい状態の両方を返し、古い状態はそのままにしておく
trait RNG {
  def nextInt: (Int, RNG)
}

線形合同法的ジェネレータ

f:id:shigemk2:20150607170616p:plain