第 12 章 ストリームによる計算

前の章で、変数、代入、および状態を持つオブジェクトを紹介しました。時間とともに変化する実世界のオブジェクトを、計算において変数の状態を変化させることで、モデル化できることを見ました。実世界では時刻は変化します。そのように、プログラム実行における時刻の変化によって、実世界の時刻変化をモデル化できます。もちろん、そのような時刻変化は、通常伸びたり縮んだりしますが、相対的な順番は守られます。これはまったく自然に見えますが、注意すべき大事なことがあります。 いったん変数と代入を導入すると、我々のシンプルでパワフルな関数ベースの計算の置き換えモデルは、もはや適用できないのです。

ほかに方法はないのでしょうか？ 実世界の状態変化を、状態を持たない関数を使ってモデル化できないでしょうか？ 数学の導きによると、答えは明らかに Yes です。時間変化する量は、時刻 t をパラメータにとる関数 f(t) によって、シンプルにモデル化できます。モデル化だけでなく計算においても、これはうまくいきます。変数を次々と書き換える代わりに、それらすべての値をリストの連続的な要素として表現できます。つまり、ミュータブルな変数 var x: T は、イミュータブルの値 val x: List[T] で置き換えることができます。ある意味、空間と時間の取引です。変数に代入される様々な値は、リスト中に異なる要素として同時に存在することになります。リストベースモデルの利点の一つは、「タイムトラベル」、つまり変数に代入される連続的な値を同時に見ること、ができることです。ほかの利点としては、強力なリスト処理関数ライブラリを利用して、しばしば計算をシンプルにできることです。たとえば、特定の範囲にある素数すべての和を計算する、命令型プログラムを考えてみましょう。

def sumPrimes(start: Int, end: Int): Int = { var i = start var acc = 0 while (i < end) { if (isPrime(i)) acc += i i += 1 } acc }

変数 i が、範囲[start .. end-1]のすべての値を「経験」していることに注意してください。より関数的な方法では、変数 i の値のリストを range(start, end) によって直接に表現します。

def sumPrimes(start: Int, end: Int) = sum(range(start, end) filter isPrime)

あきらかにプログラムは短くて明快になりました! しかし、この関数型プログラムは効率の点でかなり劣ります。範囲内のすべての数からなるリストを作り、さらにそのうちの素数すべてからなるリストを作るからです。効率の点ではさらに悪いことがあります。次の例を見てください。

1000から10000の間の二番目の素数を見つける。

range(1000, 10000) filter isPrime at 1

これは、1000 から 10000 までのすべての数からなるリストが作りますが、そのリストのほとんどの要素は顧みられません！ しかし、あるトリックによって、これらのような例を効率的に実行できます。

シーケンスの後の要素が実際には計算に必要なければ、その計算を回避できるのです。

このようなシーケンスのために新しいクラスを定義します。それを Stream と呼びます。Stream は定数 empty とコンストラクタ cons を使って生成します。これらは scala.Stream モジュールで定義されています。たとえば、次の式は 1 と 2 を要素とするストリームを生成します。

Stream.cons(1, Stream.cons(2, Stream.empty))

ほかの例として、List.range の類似物、ただしリストの代わりにストリームを返すものは、次のようになります。

def range(start: Int, end: Int): Stream[Int] = if (start >= end) Stream.empty else Stream.cons(start, range(start + 1, end))

(この関数は、上のモジュール Stream でも定義されています) Stream.range と List.range は似ていますが、その実行時の振る舞いはまったく違います。

Stream.range は、最初の要素が start である Stream オブジェクトを直ちに返します。そのほかのすべての要素は、tail メソッド呼び出しによって、それらが 必要 になったときにのみ計算されます (tail メソッドはまったく呼ばれないかもしれません) 。

ストリームは単なるリストとしてアクセスされます。リストと同様、基本的なアクセスメソッドは isEmpty と head と tail です。たとえば次のようにして、ストリームのすべての要素を表示できます。

def print(xs: Stream[A]) { if (!xs.isEmpty) { Console.println(xs.head); print(xs.tail) } }

ストリームは、リストに対して定義されている他のほぼすべてのメソッドもサポートしています (これらがサポートするメソッドの差分については、下記を参照してください) 。たとえば、1000 から 10000 の範囲のストリームに filter と apply を適用して、1000 から 10000 の間の二番目の素数を見つけることができます。

Stream.range(1000, 10000) filter isPrime at 1

先のリストベースの実装との違いは、もはや不必要に三番目以降を構築して素数判定しないことです。

ストリームの CONS と連結 クラス List のメソッドのうち、クラス Stream ではサポートされていないものは、:: と ::: の２つです。理由は、これらのメソッドは右側の引数に対して呼ばれるからです。右側の引数に対して呼ばれるということは、その引数は、メソッドが呼ばれる前に評価される必要があるということです。たとえばリストの x :: xs の場合、後部 xs は :: が呼ばれる前に評価される必要があり、新しいリストが構築される場合があります。これはストリームではうまくいきません。ストリームの後部は、それが tail オペレーションによって必要となるまでは評価されてはなりません。リストの連結 ::: をストリームに持ち込めないのも、同じ理由です。

x :: xs の代わりに、最初の要素 x と (未評価の) 後部 xs からなるストリームを構築するには、Stream.cons(x, xs) を使います。xs ::: ys の代わりに、オペレーション xs append ys を使います。