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 の評価がどうされるかを最後に確認しておく。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です