「Chapter 12 Computing with Streams」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* Chapter 12 Computing with Streams
The previous chapters have introduced variables, assignment and stateful objects. We have seen how real-world objects that change with time can be modeled by changing the state of variables in a computation. Time changes in the real world thus are modeled by time changes in program execution. Of course, such time changes are usually stretched out or compressed, but their relative order is the same. This seems quite natural, but there is a also price to pay: Our simple and powerful substitution model for functional computation is no longer applicable oncewe introduce variables and assignment.
前の章で、変数、代入、および状態を持つオブジェクト、を紹介しました。我々は、時間とともに変化する実世界のオブジェクトを、計算において変数の状態を変化させる事でモデル化できる事を見ました。実世界では時刻は変化します。そのため、プログラム実行における時刻の変化によって、現実世界の時刻の変化をモデル化できます。もちろん、そのような時刻の変化は、通常伸びたり縮んだりしますが、相対的な順番は守られます。これはまったく自然に見えますが、注意すべき大事な事があります：いったん変数と代入を導入してしまうと、我々のシンプルでパワフルな関数ベース計算の置き換えモデルは、もはや適用できないのです。
Is there another way? Can we model state change in the real world using only immutable functions? Taking mathematics as a guide, the answer is clearly yes: A time-changing quantity is simply modeled by a function f(t) with a time parameter t. The same can be done in computation. Instead of overwriting a variable with successive values, we represent all these values as successive elements in a list. So,
a mutable variable var x: T gets replaced by an immutable value val x: List[T]. In a sense, we trade space for time – the different values of the variable now all exist concurrently as different elements of the list. One advantage of the list-based view is that we can “time-travel”, i.e. view several successive values of the variable at the
same time. Another advantage is that we canmake use of the powerful library of list processing functions, which often simplifies computation. For instance, consider the imperative way to compute the sum of all prime numbers in an interval:
ほかに方法はないのでしょうか？実世界の状態変化を、状態を持たない関数を使ってモデル化できないでしょうか？数学の導きを頼ると、答えは明確に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
}
Note that the variable i “steps through” all values of the interval [start .. end1].
A more functional way is to represent the list of values of variable i directly as range(start, end). Then the function can be rewritten as follows.
変数iが、範囲[start .. end-1]のすべての値を「経験」している事に注意してください。より関数的な方法では、変数iの値のリストを直接range(start, end)によって表現します。
def sumPrimes(start: Int, end: Int) =
sum(range(start, end) filter isPrime)
No contest which program is shorter and clearer! However, the functional program is also considerably less efficient since it constructs a list of all numbers in the interval, and then another one for the prime numbers. Even worse from an efficiency point of view is the following example:
あきらかにプログラムが短くて明快になりました！しかし、この関数型プログラムは効率性の点で劣ります。範囲内のすべての数を持つリストを作り、さらにそのうちの素数すべてのリストを作るからです。効率の点ではさらに悪い事があります。次の例を見てください。
To find the second prime number between 1000 and 10000:
1000から10000の間の２番目の素数を見つける:
range(1000, 10000) filter isPrime at 1
Here, the list of all numbers between 1000 and 10000 is constructed. But most of that list is never inspected!
However, we can obtain efficient execution for examples like these by a trick:
これでは、1000から10000までのすべての数を持つリストが作られますが、そのリストのほとんどの要素は顧みられません！
しかし、あるトリックによって、これらのような例を効率的に実行する事ができます:
Avoid computing the tail of a sequence unless that tail is actually necessary for the computation.
列の残りの要素が実際に計算に必要なければ、それを計算する事を回避する
We define a new class for such sequences, which is called Stream. Streams are created using the constant empty and the constructor cons, which are both defined in module scala.Stream. For instance, the following expression constructs a stream with elements 1 and 2:
このような列のため新しいクラスを定義します。それをStreamと呼びます。
Streamは定数emptyとコンストラクタconsを使って生成します。これらはscala.Streamモジュールに定義されています。たとえば、次の式は1と2を要素とするストリームを生成します。
Stream.cons(1, Stream.cons(2, Stream.empty))
As another example, here is the analogue of List.range, but returning a stream instead of a list:
ほかの例として、List.rangeの類似物、ただしリストの代わりにストリームを返す物はこのようになります:
def range(start: Int, end: Int): Stream[Int] =
if (start >= end) Stream.empty
else Stream.cons(start, range(start + 1, end))
(This function is also defined as given above in module Stream). Even though Stream.range and List.range look similar, their execution behavior is completely different:
（この関数は、上記のモジュールStreamにも定義されています）Stream.rangeとList.rangeは似ていますが、その実行の振る舞いはまったく異なります:
Stream.range immediately returns with a Stream object whose first element is start. All other elements are computed only when they are demanded by calling the tail method (which might be never at all).
Streams are accessed just as lists. Similarly to lists, the basic access methods are isEmpty, head and tail. For instance, we can print all elements of a stream as follows.
Stream.rangeは最初の要素がstartであるStreamオブジェクトを直ちに返します。そのほかのすべての要素は、tailメソッド呼び出しによってそれらが必要になったときにのみ計算されます（tailメソッドはまったく呼ばれないかもしれません）。
ストリームは単に利宇sととしてアクセスされます。リストと同様、基本的なアクセスメソッドはisEmptyとheadとtailです。たとえば、次のようにしてストリームのすべての要素を表示できます。
def print(xs: Stream[A]) {
if (!xs.isEmpty) { Console.println(xs.head); print(xs.tail) }
}
Streams also support almost all other methods defined on lists (see below for where their methods sets differ). For instance, we can find the second prime number between 1000 and 10000 by applying methods filter and apply on an interval stream:
ストリームはリストについて定義されているほかのほぼすべてのメソッドもサポートしています（これらがサポートするメソッドの差分は下記を参照してください）。たとえば、1000から10000の範囲のストリームにfilterとapplyを適用する事で、1000から10000の間の２番目の素数を見つけることができます:
Stream.range(1000, 10000) filter isPrime at 1
The difference to the previous list-based implementation is that now we do not needlessly construct and test for primality any numbers beyond 3.
さきのリストベースの実装との違いは、もはや不必要に3番目以降を構築して素数判定を行ったりしない事です。
''Consing and appending streams.'' Two methods in class List which are not supported by class Stream are :: and :::. The reason is that these methods are dispatched on their right-hand side argument, whichmeans that this argument needs to be evaluated before the method is called. For instance, in the case of x :: xs on lists, the tail xs needs to be evaluated before :: can be called and the new list can be constructed. This does not work for streams, where we require that the tail of a stream should not be evaluated until it is demanded by a tail operation. The argument why list-append ::: cannot be adapted to streams is analogous.
クラスListのふたつのメソッドのうち、クラスStreamではサポートされていないものは、::と:::です。理由は、これらのメソッドは右側の引数に対して呼ばれるからです。右側の引数に対して呼ばれるということは、その引数はメソッドが呼ばれる前に評価される必要があるという事です。たとえばリストの x :: xs を考えると、残部であるxsは::が呼び出される前に評価される必要があり、新しいリストが構築される場合があります。これはストリームではうまくいきません。ストリームの残部はそれがtailオペレーションによって必要となるまでは評価されてはなりません。リストの連結:::がストリームに適用できないのも、同様の議論となります。
Instead of x :: xs, one uses Stream.cons(x, xs) for constructing a stream with first element x and (unevaluated) rest xs. Instead of xs ::: ys, one uses the operation xs append ys.
x :: xsの代わりに、最初の要素xと（未評価の）残部xs からなるストリームを構築するには、Stream.cons(x, xs)を使います。xs ::: ysの代わりに、xs append ysのオペレーションを使用します。
#co(){
Chapter 12 Computing with Streams
The previous chapters have introduced variables, assignment and stateful objects. We have seen how real-world objects that change with time can be modeled by changing the state of variables in a computation. Time changes in the real world thus are modeled by time changes in program execution. Of course, such time changes are usually stretched out or compressed, but their relative order is the same. This seems quite natural, but there is a also price to pay: Our simple and powerful substitution model for functional computation is no longer applicable oncewe introduce variables and assignment.
}
#setmenu2(ex-r-menu)
* 第 12 章 ストリームによる計算 (Computing with Streams)
前の章で、変数、代入、および状態を持つオブジェクトを紹介しました。時間とともに変化する実世界のオブジェクトを、計算において変数の状態を変化させることで、モデル化できることを見ました。実世界では時刻は変化します。そのように、プログラム実行における時刻の変化によって、実世界の時刻変化をモデル化できます。もちろん、そのような時刻変化は、通常伸びたり縮んだりしますが、相対的な順番は守られます。これはまったく自然に見えますが、注意すべき大事なことがあります。 いったん変数と代入を導入すると、我々のシンプルでパワフルな関数ベースの計算の置き換えモデルは、もはや適用できないのです。
#co(){
Is there another way? Can we model state change in the real world using only immutable functions? Taking mathematics as a guide, the answer is clearly yes: A time-changing quantity is simply modeled by a function f(t) with a time parameter t. The same can be done in computation. Instead of overwriting a variable with successive values, we represent all these values as successive elements in a list. So,
a mutable variable var x: T gets replaced by an immutable value val x: List[T]. In a sense, we trade space for time - the different values of the variable now all exist concurrently as different elements of the list. One advantage of the list-based view is that we can "time-travel", i.e. view several successive values of the variable at the same time. Another advantage is that we can make use of the powerful library of list processing functions, which often simplifies computation. For instance, consider the imperative way to compute the sum of all prime numbers in an interval:
}
ほかに方法はないのでしょうか？ 実世界の状態変化を、状態を持たない関数を使ってモデル化できないでしょうか？ 数学の導きによると、答えは明らかに 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
}
#co(){
Note that the variable i "steps through" all values of the interval [start .. end1].A more functional way is to represent the list of values of variable i directly as range(start, end). Then the function can be rewritten as follows.
}
変数 i が、範囲[start .. end-1]のすべての値を「経験」していることに注意してください。より関数的な方法では、変数 i の値のリストを range(start, end) によって直接に表現します。
def sumPrimes(start: Int, end: Int) =
sum(range(start, end) filter isPrime)
#co(){
No contest which program is shorter and clearer! However, the functional program is also considerably less efficient since it constructs a list of all numbers in the interval, and then another one for the prime numbers. Even worse from an efficiency point of view is the following example:
}
あきらかにプログラムは短くて明快になりました! しかし、この関数型プログラムは効率の点でかなり劣ります。範囲内のすべての数からなるリストを作り、さらにそのうちの素数すべてからなるリストを作るからです。効率の点ではさらに悪いことがあります。次の例を見てください。
#co(){
To find the second prime number between 1000 and 10000:
}
1000から10000の間の二番目の素数を見つける。
range(1000, 10000) filter isPrime at 1
#co(){
Here, the list of all numbers between 1000 and 10000 is constructed. But most of that list is never inspected!
However, we can obtain efficient execution for examples like these by a trick:
}
これは、1000 から 10000 までのすべての数からなるリストが作りますが、そのリストのほとんどの要素は顧みられません！
しかし、あるトリックによって、これらのような例を効率的に実行できます。
#co(){
Avoid computing the tail of a sequence unless that tail is actually necessary for the computation.
}
シーケンスの後の要素が実際には計算に必要なければ、その計算を回避できるのです。
#co(){
We define a new class for such sequences, which is called Stream. Streams are created using the constant empty and the constructor cons, which are both defined in module scala.Stream. For instance, the following expression constructs a stream with elements 1 and 2:
}
このようなシーケンスのために新しいクラスを定義します。それを Stream と呼びます。Stream は定数 empty とコンストラクタ cons を使って生成します。これらは scala.Stream モジュールで定義されています。たとえば、次の式は 1 と 2 を要素とするストリームを生成します。
Stream.cons(1, Stream.cons(2, Stream.empty))
#co(){
As another example, here is the analogue of List.range, but returning a stream instead of a list:
}
ほかの例として、List.range の類似物、ただしリストの代わりにストリームを返すものは、次のようになります。
def range(start: Int, end: Int): Stream[Int] =
if (start >= end) Stream.empty
else Stream.cons(start, range(start + 1, end))
#co(){
(This function is also defined as given above in module Stream). Even though Stream.range and List.range look similar, their execution behavior is completely different:
}
(この関数は、上のモジュール Stream でも定義されています) Stream.range と List.range は似ていますが、その実行時の振る舞いはまったく違います。
#co(){
Stream.range immediately returns with a Stream object whose first element is start. All other elements are computed only when they are demanded by calling the tail method (which might be never at all).
Streams are accessed just as lists. Similarly to lists, the basic access methods are isEmpty, head and tail. For instance, we can print all elements of a stream as follows.
}
Stream.range は、最初の要素が start である Stream オブジェクトを直ちに返します。そのほかのすべての要素は、tail メソッド呼び出しによって、それらが&bold(){必要}になったときにのみ計算されます (tail メソッドはまったく呼ばれないかもしれません) 。
ストリームは単なるリストとしてアクセスされます。リストと同様、基本的なアクセスメソッドは isEmpty と head と tail です。たとえば次のようにして、ストリームのすべての要素を表示できます。
def print(xs: Stream[A]) {
if (!xs.isEmpty) { Console.println(xs.head); print(xs.tail) }
}
#co(){
Streams also support almost all other methods defined on lists (see below for where their methods sets differ). For instance, we can find the second prime number between 1000 and 10000 by applying methods filter and apply on an interval stream:
}
ストリームは、リストに対して定義されている他のほぼすべてのメソッドもサポートしています (これらがサポートするメソッドの差分については、下記を参照してください) 。たとえば、1000 から 10000 の範囲のストリームに filter と apply を適用して、1000 から 10000 の間の二番目の素数を見つけることができます。
Stream.range(1000, 10000) filter isPrime at 1
#co(){
The difference to the previous list-based implementation is that now we do not needlessly construct and test for primality any numbers beyond 3.
}
先のリストベースの実装との違いは、もはや不必要に三番目以降を構築して素数判定しないことです。
#co(){
Consing and appending streams. Two methods in class List which are not supported by class Stream are :: and :::. The reason is that these methods are dispatched on their right-hand side argument, which means that this argument needs to be evaluated before the method is called. For instance, in the case of x :: xs on lists, the tail xs needs to be evaluated before :: can be called and the new list can be constructed. This does not work for streams, where we require that the tail of a stream should not be evaluated until it is demanded by a tail operation. The argument why list-append ::: cannot be adapted to streams is analogous.
}
&b(){ストリームの CONS と連結 } クラス List のメソッドのうち、クラス Stream ではサポートされていないものは、:: と ::: の２つです。理由は、これらのメソッドは右側の引数に対して呼ばれるからです。右側の引数に対して呼ばれるということは、その引数は、メソッドが呼ばれる前に評価される必要があるということです。たとえばリストの x :: xs の場合、後部 xs は :: が呼ばれる前に評価される必要があり、新しいリストが構築される場合があります。これはストリームではうまくいきません。ストリームの後部は、それが tail オペレーションによって必要となるまでは評価されてはなりません。リストの連結 ::: をストリームに持ち込めないのも、同じ理由です。
#co(){
Instead of x :: xs, one uses Stream.cons(x, xs) for constructing a stream with first element x and (unevaluated) rest xs. Instead of xs ::: ys, one uses the operation xs append ys.
}
x :: xs の代わりに、最初の要素 x と (未評価の) 後部 xs からなるストリームを構築するには、Stream.cons(x, xs) を使います。xs ::: ys の代わりに、オペレーション xs append ys を使います。
#center(){[[前ページ>Example11.4]] [[ 12 章>Chapter 12 Computing with Streams]] [[目次>ScalaByExample和訳]] [[次ページ>Chapter 13 Iterators]]}
----
#comment
