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

新人SEの学習記録

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

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

学習記録 関数型 プログラミング Scala

第5章:正格と遅延

一組のトランプから奇数のカードを抜き取り,クイーンのカードを全て裏返すよう言われた時,
理想的には全てのカードを通しで調べる際に奇数のカードとクイーンのカードを同時に探したい。
しかし,Scalaが以下のコードで行っているのは,奇数のカードを抜き取った後,残りのカードからクイーンを探す行為である。

scala> List(1,2,3,4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3)
res0: List[Int] = List(36,42)

上の式では,map(_ + 10)が中間リスト(11,12,13,14)を生成し,そのリストがfilter(_ % 2 == 0)に渡され,その結果がmap(_ * 3)に渡される。
つまり,変換の度に次の変換への入力として使われるだけの一時リストが生成され,その後すぐに削除される。
こうした一連の変換をどうにかして一回の処理にまとめ,一時的なデータ構造を作成せずに済ませられないだろうか。
こうしたループの自動的な融合は,非正格性〜遅延性を使って実現できる。

本章では,非正格性がどのようなものであるかを説明し,複数の変換を融合する遅延リスト型の実装を示す。

正格関数と非正格関数

非正格性は関数の特性で,その引数の一つ以上を評価しないという選択が可能である。逆に,正格関数では,引数が常に評価される。
正格関数はほとんどのプログラミング言語の標準であり,それどころか引数が完全に評価されることを期待する関数だけをサポートする言語がほとんどである。
Scalaでも,特に明記しない限り関数定義はすべて正格である。

def square(x: Double): Double = x * x

上のsquare関数は正格であるため,square(10.0 + 1.0)という呼び出しでは計算済みの11.0という値が渡される。
square(sys.error("failure"))という呼び出しでは,squareの本体に入る前にsys.error式が評価され例外が発生する。

Scalaで非正格性を指定するための構文についてはまだ説明していないが,概念には既に馴染みがあるはずである。
例えば,短絡論理関数&&および||は非正格である。これらは引数を評価しないことを選択できる関数と考えることができる。
&&関数はBoolean型の引数を二つ受け取るが,2つ目の引数を評価するのは1つ目の引数がtrueの場合だけである。

scala> false && { println("!!"); true }
res1: Boolean = false

Scalaのif制御構造も非正格の一例である。

val result = if (input.isEmpty) sys.error("empty input") else input

ifはBoolean型の条件,条件がtrueの場合に返すA型の式,falseの場合に返すA型の式という3パラメータを受け取る関数と考えることができる。
関数としてのifは引数を全て評価しないため,非正格である(正確には,条件パラメータについては正格)。

Scalaで非正格関数を記述するには,引数の一部を評価されない状態で受け取る。
ここでは,その仕組みを示した後,Scalaに組み込まれている便利な構文をいくつか紹介する。
if文を関数で表した非正格関数if2は以下のようになる。

def if2[A](cond: Boolean, onTrue: () => A, onFalse: () => A): A = 
 if (cond) onTrue() else onFalse()

if2(a < 22,
     () => println("a"),
     () => println("b")
)

評価せずに渡したい引数の手前に() =>が付いているのがわかる。
() => A型の値は,0個の引数を受け取りAを返す関数である。評価されない形式の式を一般にサンクと呼ぶ。
サンクに対しては,式の評価と結果の取得を強制することができる。
そのためには,onTrue()のように関数を呼び出す際に空の引数リストを明示的に渡し,
同様にif2の呼び出し元サンクを明示的に作成する( () => println("a")の部分 )必要がある。

この構文によって何をしているかが非常に明確になる。
非正格パラメータの代わりに引数なしの関数を渡した後( () => A ),
この関数を本体から明示的に呼び出して結果を取得(onTrue())している。
ただし,これはよくあるケースなので,より便利な構文が用意されている。

def if2[A](cond: Boolean, onTrue: => A, onFalse: => A): A =
  if (cond) onTrue else onFalse

if2(false,
    sys.error("fail"),
    3)

評価せずに渡したい引数の方の手前に=>矢印がある。
この=>の付いた引数を評価するために関数本体で特別なことをする必要はなく,それらの識別子(onTrue)を通常通りに参照するだけである。
また,この関数を呼び出すときも何か特別なことをする必要はなく,Scalaが式をサンクで囲んでくれる。

どちらの構文でも,評価されずに関数に渡される引数は,関数の本体内で参照されている場所ごとに一回だけ評価される。
つまり,Scalaは引数の評価結果をデフォルトではキャッシュしない。

scala> def maybeTwice(b: Boolean, i: => Int) = if (b) i+i else 0
maybeTwice: (b: Boolean, i: => Int)Int

scala> val x = maybeTwice(true, { println("hi"); 1+41 })
hi
hi
x: Int = 84

この例では,引数iがmaybeTwiceの本体で2回参照されていることがわかる。
結果を1回だけ評価したい場合は,lazyキーワードを使って値を明示的にキャッシュする。

scala> def maybeTwice(b: Boolean, i: => Int) = {
     | lazy val j = i
     | if (b) j+j else 0
     | }
maybeTwice: (b: Boolean, i: => Int)Int

scala> val x = maybeTwice(true, { println("hi"); 1+41 })
hi
x: Int = 84

val宣言にlazyキーワードを追加すると,lazy val宣言の右辺の評価が最初に参照されるときまで先送りにされる。
また,その後の参照で評価を繰り返し行うことがないよう,結果がキャッシュされる。
上の例では,iの評価は最初に参照されるj+jの前のjまで先送りされ,j+jの後ろのjはキャッシュを使って評価されることになる。