タグ: fpinscala

乱数生成を純粋化する

乱数の生成についての簡単な例を見てみよう。scala.util.Random が用意されているのでそれを使えば簡単だ。

nextInt メソッドは呼び出しのたびに返ってくる値が異なる。呼び出しのたびに rng の状態が遷移していることが想像出来る。たとえば、ランダム性を利用したメソッドのテストを書こうとした場合、テストを再現可能にする必要があるが scala.util.Random では難しそうである。仮に乱数ジェネレータを直接扱うとしても、ジェネレータの状態を揃えてあげる必要がある。こういった状態に対処するために、副作用を使用しないという原点に立ち返ろう。

純粋関数型の乱数生成

状態を遷移させるのではなく、新しい状態を返すという気持ちでやっていく。乱数ジェネレータの場合は、ジェネレータの nextInt を呼び出すと、値と新しいジェネレータを返すという感じになる。もちろん、もとのジェネレータは状態遷移しない。したがって、もとのジェネレータの nextInt を何回呼び出しても、同じ値と新しいジェネレータが返ってくる。コードで表現すると次のようになる。

こいつは以下のような挙動を示す。

見ての通り、nextInt は純粋な関数になった。

ステートフルなAPIと向き合う

乱数生成の例で見たようなことと同じような方法で、すべてのステートフルAPIは純粋化できる。基本的には状態を遷移させるのではなく、値と新しい状態を返してやるという方針になる。ただし普通にこれをやってみるとボイラープレートが多くて辛い気持ちになるだろう。たとえば RandomGenerator に対していろんな便利関数を定義してみる。同じことばっかりやっているように見えないだろうか?

すべて RandomGenerator => (A, RandomGenerator) な関数になっている。「状態を遷移させるのではなく、値と新しい状態を返してやる」という方針が関数に明確に現れてきている。この部分は繰り返し出現するのですこし抽象化しよう。type を使って RandomGenerator => (A, RandomGenerator)Rand[A] というエイリアスを張り付ける。すると見なれた mapmap2 などの高階関数が定義できて、かつそれを用いて上で定義した関数などを実装できるようになる。

遅延リストを作る

FP in Scala 第5章読書会の予習。Streamの作成については、半年前くらいに記事にまとめた。

リストの操作と無駄な中間リスト

リストへのmapやfilter操作の評価は、模式的には以下のような感じで行われる。

中間リストが無駄に生成されているので、mapやfilterといった高階関数をつかって合成性をおとさずに、つまりwhileループに頼らずなんとかしたい。そんなときに非正格性(non-strictness)を使うとよい。ということで「ワンランク上のリストの構築のしかた」を探っていく。

正格関数と非正格関数

「ワンランク上のリスト構築」をする前に正格性について確認を行っておく。
正格性とは関数の特性である。非正格関数では、引数の1つ以上を評価しないという選択が可能で、正格関数では引数が常に評価される。

Scalaの if 制御構造は非正格の一例。array.isEmpty の状態に応じて、then または else のステートメントが評価されない。

正確には、条件パラメータについては常に正格であり、各条件分岐後のステートメントは非正格である。Scalaで非正格関数を記述するためには、引数の一部を評価されない状態で受け取ればよい。具体的には以下のようにできる。

評価されない式をサンクとよぶ。これを評価するためには、空の引数リストを渡せばよい。() => A は実際には Function0[A] 型のシンタックスシュガーになっている。上の if2 関数はさらに簡単に以下のように書ける。

どちらの構文においても、評価されずに渡される引数は、関数の本体ないで参照されている場所ごとに毎回評価される。これを避けるためには、lazy キーワードを使って値を明示的にキャッシュすればよい。

遅延リストを作る

非正格にする方法はわかっているので、あとはリストでやったことに手を加えてやれば良い。
データ構造の定義は以下のとおり。

これを用いて、冒頭で示したリストへの操作の効率化を図っていくことを考える。

コンストラクタに潜む非効率性

Consデータコンストラクタを直接呼び出した場合、評価が無駄に走ることがある。

無駄な処理を減らすためにはキャッシュをさせてやればよい。以下のようにスマートコンストラクタを定義する。

Empty のスマートコンストラクタには型推論を助ける狙いもある。これらを用いると以下のようにできる。

各種関数の定義

foldRightmap, flatMap などを定義する

評価のされ方

以上のようにして定義した Stream の評価がどうされるかを最後に確認しておく。