読者です 読者をやめる 読者になる 読者になる

新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。気づけば社会人3年目に突入。

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

第5章:正格と遅延

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

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

もう少し一般的な言い方をすれば,遅延を利用することで式の記述をその式の評価から切り離すことが可能になる。
それにより,必要以上に大きな式を表現し,その一部だけを評価できるようになる。
例として,exists関数を見てみる。

def exists(p: A => Boolean): Boolean = this match {
  case Cons(h, t) => p(h()) || t().exists(p)
  case _ => false
}

この関数は,Boolean関数とマッチする要素がこのStreamに存在するかどうかをチェックする。
"||"が第2引数に関して非正格であるので,p(h())がtrueを返した場合,existsは走査をそこで中断してtrueを返す。
つまり,走査が途中で終了するだけでなく,ストリームの末尾がまったく評価されないことになる。

このexists関数は明示的な再帰を使って実装されている。
第3章のListではではfoldRight形式の汎用的な再帰を実装したが,Streamでも同じことを実現できる。

// 関数fはA型とB型の引数をとり,B型を返す。
// B型の引数の前には=>が付いており,遅延評価される。
def foldRight[B](z: => B)(f: (A, => B) => B): B =
  this match {
    case Cons(h, t) => f(h(),  t().foldRight(z)(f))
    case _ => z
  }

結合関数fが第2パラメータに関して非正格であるため,
fが第2パラメータを評価しないことを選択した場合,走査はそこで終了する。
foldRightを使ってexistsを実装すれば,これを確認できる。

def exists(p: A => Boolean): Boolean = 
  foldRight(false)((a, b) => p(a) || b)

この場合のbはストリームの末尾を抱える評価されない再帰ステップである。
p(a)がtrueを返した場合,bは評価されず,計算はそこで終了する。

Exercise 5.4
  • Streamの要素のうち,指定された述語とマッチするものを全てチェックするforAllを実装せよ。

この関数でも,マッチしない値が検出された時点でチェックを終了する必要がある。

  def forAll(p: A => Boolean): Boolean =
    foldRight(true)((a,b) => p(a) && b)

全ての要素について走査が終われば,一つ目の括弧に書かれたtrueを返す。
途中でp(a)がfalseになればそこで走査が中断され(&&は非正格なので),falseを返す。

scala> val x: holder.Stream[Int] = holder.Stream(1,2,3,4,5,6,7,8,9)
x: holder.Stream[Int] = Cons(<function0>,<function0>)

scala> x.forAll(a => a % 2 == 0)
res0: Boolean = false

scala> x.forAll(a => a <= 9)
res1: Boolean = true

scala> x.forAll(a => a <= 8)
res2: Boolean = false
Exercise 5.5
  • foldRightを使ってtakeWhileを実装せよ。

最初にEmptyを渡し,そこに関数pに当てはまる要素を追加していく。

  def takeWhile(p: A => Boolean): Stream[A] =
    foldRight(holder.Stream.empty[A])((a,b)
      => if (p(a)) holder.Stream.cons(a, b) else holder.Stream.empty[A])

このtakeWhile関数の実行結果として得られたStreamの要素を他の処理が調べるまで,
そのStreamを実際に生成する処理は実行されないことに注目してほしい。
こうした漸進的な性質のおかげで,中間結果を完全にインスタンス化することなく,これらの関数を次々に呼び出すことが可能である。

本章で最初に示したStream(1,2,3,4).map(_ + 10).filter(_ % 2 == 0)という例の簡単なトレースを見てみる。
最終的にtoListを使ってListに変換することでStreamを強制的に評価している。

Stream(1,2,3,4).map(_ + 10).filter(_ % 2 == 0).toList

// mapを1つ目の要素に適用
cons(11, Stream(2,3,4).map(_ + 10)).filter(_ % 2 == 0).toList

// filterを1つ目の要素に適用
Stream(2,3,4).map(_ + 10).filter(_ % 2 == 0).toList

// mapを2つ目の要素に適用
cons(12, Stream(3,4).map(_ + 10)).filter(_ % 2 == 0).toList

// filterを2つ目の要素に適用し,結果の1つ目の要素を生成
12 :: Stream(3,4).map(_ + 10).filter(_ % 2 == 0).toList

// mapを3つ目の要素に適用
12 :: cons(13, Stream(4).map(_ + 10)).filter(_ % 2 == 0).toList

// filterを3つ目の要素に適用
12 :: Stream(4).map(_ + 10).filter(_ % 2 == 0).toList

// mapを4つ目の要素に適用
12 :: cons(14, Stream().map(_ + 10)).filter(_ % 2 == 0).toList

// filterを2つ目の要素に適用し,結果の最後の要素を生成
12 :: 14 :: Stream().map(_ + 10).filter(_ % 2 == 0).toList

// mapとfilterの処理が終了し,空のストリームが空のリストに変換される
12 :: 14 :: List()

このトレースでは,filterとmapの変換が交互に実行されている。
mapの出力として要素を1つ生成する作業と,その要素が2で割り切れるかどうか確認するfilterでの評価が交互に行われている。
要素が2で割り切れる場合は出力リストに追加される。

このとき,mapの結果として得られる中間ストリームを完全にインスタンス化していないことに注目してほしい。
これは特殊なループを使って処理を差し込むのと同じで,ストリームがファーストクラスループと呼ばれるのはこのためである。

中間ストリームがインスタンス化されないため,必要以上に処理されることを心配せずに既存のコンビネータを再利用できる。
例えば,マッチする要素が存在する場合にその最初の要素だけを返すfindメソッドを定義する。
この定義にはfilterを再利用でき,filterはストリーム全体を変換するが,この変換は遅延方式で行われるため,
findはマッチするものを検出した時点で終了する。

def find(p: A => Boolean): Option[A] =
  filter(p).headOption

ストリーム変換の漸進的な性質はメモリの使い方にも重大な影響を及ぼす。
中間ストリームを生成しないので,現在の要素を格納して変換するのに必要な作業メモリだけで済む。
例えば,

Stream(1,2,3,4).map(_ + 10).filter(_ % 2 == 0)

この変換では,mapによって11と13の値が出力され,それらの値にメモリ領域が割り当てられるが,
これらの流域はfilterによって不要と判断された時点で解放できる。