今回は Scala の「遅延評価 (delayed evaluation または lazy evaluation)」について説明します。
一般的なプログラミング言語の場合、関数を呼び出す前に引数が評価され、その結果が関数に渡されます。これを「正格 (strict) な評価」といいます。Scala は正格評価ですが、「名前渡しパラメータ」という機能を使うと、その値が必要になるまで引数の評価は行われません。名前渡しパラメータの構文を示します。
引数: => 型
名前渡しパラメータは 引数: と 型 の間に => を指定します。これでこの引数は「遅延評価」されます。具体的には、引数を参照するときに評価が行われます。そして、その評価結果は保存されることに注意してください。再度引数を参照すると、保存されている値が返されます。
遅延評価は関数の引数を評価するときだけではなく、変数の値を評価するときにも行われます。Scala の場合、変数宣言の前にキーワード lazy を付けます。これで変数を参照するまで評価が遅延されます。
簡単な例を示しましょう。
scala> lazy val x = {println("oops!"); 10 + 20}
lazy val x: Int // unevaluated
scala> x
oops!
val res0: Int = 30
scala> x
val res1: Int = 30
10 + 20 の結果を変数 x にセットします。このとき、式 10 + 20 は評価されていないことに注意してください。(単純な式であればコンパイルの段階で計算されることがあります。) x を参照すると式 10 + 20 を評価して値 30 が得られます。このとき、oops! が表示されます。x を再度参照すると、式を評価せずに保存した値を返すので oops! は表示されません。
もうひとつ簡単な例を示しましょう。
scala> lazy val a = {println("oops-a"); 10}
lazy val a: Int // unevaluated
scala> lazy val b = {println("oops-b"); 20}
lazy val b: Int // unevaluated
scala> lazy val c = {println("oops-c"); 30}
lazy val c: Int // unevaluated
scala> def add3(x: => Int, y: => Int, z: => Int): Int = x + y
def add3(x: => Int, y: => Int, z: => Int): Int
scala> add3(a, b, c)
oops-a
oops-b
val res2: Int = 30
関数 add3 は 3 つの引数 x, y, z を名前渡しで受け取りますが、x と y しか参照していません。この場合、引数 z は評価されません。実際、add3(a, b, c) を評価すると、変数 a, b は評価されて oops-a, oops-b が表示されますが oops-c は表示されないので、変数 c は評価されていないことがわかります。
それでは、遅延評価の簡単な例題として「たらいまわし関数」を取り上げます。次のリストを見てください。
リスト : たらいまわし関数
def tarai(x:Int, y:Int, z:Int): Int =
if (x <= y) y
else tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y))
def tak(x:Int, y:Int, z:Int): Int =
if (x <= y) z
else tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y))
前回は関数 tak を「メモ化」で高速化しました。これに対し、関数 tarai は遅延評価を行う処理系では高速に実行できることが知られています。正格な評価を行うプログラミング言語では時間がかかっても、Scala の遅延評価を使えばあっというまに計算することができます。
tarai のプログラムを見てください。x <= y のときに y を返しますが、このとき引数 z の値は必要ありませんね。引数 z を名前渡しパラメータにすれば、x > y のときにだけ引数 z を評価するので、無駄な計算を省略することができます。なお、関数 tak は x <= y のときに z を返しているため、遅延評価で高速化することはできません。ご注意ください。
プログラムは次のようになります。
リスト : たらいまわし関数 (遅延評価)
def taraiLazy(x: Int, y: Int, z: => Int): Int =
if (x <= y) y
else taraiLazy(taraiLazy(x - 1, y, z),
taraiLazy(y - 1, z, x),
taraiLazy(z - 1, x, y))
引数 z を名前渡しパラメータに指定するだけです。これで taraiLazy の第 3 引数が遅延評価され、必要になったときにだけ z が評価されます。
それでは実行してみましょう。
tarai(16, 8, 0) : 49.0 [s] taraiLazy(16, 8, 0) : 0.003 [s] 実行環境 : Ubunts 18.04 (WSL), Intel Core i5-6200U 2.30GHz
結果は一目瞭然で、tarai は約 50 秒かかりますが、taraiLazy は瞬時に計算を終えてしまいます。興味のある方はいろいろ試してみてください。
「ストリーム (stream)」はデータの流れを抽象化したデータ構造です。たとえば、ファイル入出力はストリームと考えることができます。また、リストを使ってストリームを表すこともできます。ただし、単純なリストでは有限個のデータの流れしか表すことができません。ところが、遅延評価を用いると擬似的に無限個のデータを表すことができるようになります。これを「遅延ストリーム」とか「遅延リスト」と呼びます。
なお、Scala のライブラリ scala.collection.immutable には遅延ストリーム Stream [*1] と LazyList が用意されているので、わざわざ自作する必要はないのですが、今回は Scala のお勉強ということで、シンプルな遅延ストリームを作ってみましょう。
遅延ストリームの基本的な考え方は、必要になったときに新しいデータを生成することです。このときに遅延評価を用います。具体的にはデータを生成する関数を用意し、それを遅延評価してストリームに格納しておきます。そして、必要になった時点で遅延評価しておいた関数を呼び出して値を求めればよいわけです。
今回は immutable な連結リストと同じ構造で遅延ストリームを表すことにします。コンスセルの CAR 部が現時点での先頭データを表し、CDR 部に遅延ストリームを生成する関数を格納します。次のリストを見てください。
リスト : 遅延ストリーム
package lazylist
// 抽象クラス
abstract class LazyList[+A] {
def car: A
def cdr: LazyList[A]
def isEmpty: Boolean
//
// メソッドの定義 (省略)
//
}
// セル
class Cons[A] private (a: A, b: => LazyList[A]) extends LazyList[A] {
lazy val c = b
def car: A = a
def cdr: LazyList[A] = c
def isEmpty: Boolean = false
override def toString: String = "Cons(" + a + ", ?)"
}
object Cons {
def apply[A](a: A, b: => LazyList[A]) = new Cons(a, b)
}
// 終端 (空のストリーム)
case object Nils extends LazyList[Nothing] {
def car = throw new Exception("Empty LazyList")
def cdr = throw new Exception("Empty LazyList")
def isEmpty: Boolean = true
}
遅延ストリームの型は LazyList[A] としました。クラス名は Scala のライブラリ LazyList と同じですが、仕様は異なることに注意してください。これはあとで説明します。
LazyList は抽象クラスです。メソッド car で先頭データを取り出し、メソッド cdr で CDR 部に格納されている関数を評価して LazyList を生成します。メソッド isEmpty は遅延ストリームが終端に達したら true を返します。
クラス Cons は遅延ストリームのセルを表します。遅延ストリームはコンストラクタ Cons で生成します。引数 a が遅延ストリームの先頭データになります。引数 b は遅延ストリームを生成する関数を名前渡しで受け取ります。基本コンストラクタでは、遅延評価するフィールド変数 c に引数 b をセットします。このとき、引数 b はまだ評価されないことに注意してください。
メソッド toString は CAR 部の要素 a だけを表示します。CDR 部まで表示しようとすると、評価を遅延している変数 c を評価することになり、遅延ストリームとして機能しなくなります。
メソッド car は引数 a の値を返すだけです。メソッド cdr はフィールド変数 c の値を返します。最初に変数 c を参照するとき、引数 b の関数が評価されて、変数 c の値が決まります。この値はキャッシュされるので、このあと変数 c を何度も参照しても、引数 b の関数は評価されずに、キャッシュされた値が返されます。
Cons のメソッド isEmpty は false を返します。遅延ストリームの終端はシングルトンオブジェクト Nils で表します。car と cdr はエラーを送出し、メソッド isEmpty は true を返します。Cons, car, cdr はリスト操作の演算子 :: とメソッド head, tail に対応します。
それでは、遅延ストリームを生成する関数を作りましょう。たとえば、n から m までの整数列を生成するストリームは次のようにプログラムすることができます。
scala> import lazylist._
import lazylist._
scala> def intgen(n: Int, m: Int): LazyList[Int] =
| if (n > m) Nils else Cons(n, intgen(n + 1, m))
def intgen(n: Int, m: Int): lazylist.LazyList[Int]
関数 intgen は遅延ストリームを生成して返します。Cons の第 1 引数がストリームの初期値になります。そして、Cons の第 2 引数を cdr で評価すると、intgen(n + 1, m) が評価されて次のデータを格納した遅延ストリームが返されます。そして、それを再度 cdr で評価すると、その次のデータを得ることができます。
簡単な例を示しましょう。
scala> val a = intgen(1, 10) val a: lazylist.LazyList[Int] = Cons(1, ?) scala> a.car val res0: Int = 1 scala> val b = a.cdr val b: lazylist.LazyList[Int] = Cons(2, ?) scala> b.car val res1: Int = 2 scala> val c = b.cdr val c: lazylist.LazyList[Int] = Cons(3, ?) scala> c.car val res2: Int = 3
このように、メソッド cdr 実行することで、次々とデータを生成することができます。
もう一つ、簡単な例を示しましょう。フィボナッチ数列を生成する遅延ストリームを作ります。次の例を見てください。
scala> def fibgen(a: BigInt, b: BigInt): LazyList[BigInt] =
| Cons(a, fibgen(b, a + b))
def fibgen(a: BigInt, b: BigInt): lazylist.LazyList[BigInt]
関数 fibgen の引数 a がフィボナッチ数列の最初の項で、b が次の項です。したがって、Cons の第 2 引数に fibgen(b, a + b) を格納しておけば、cdr を適用することでフィボナッチ数列を生成することができます。Scala は多倍長整数をサポートしているので、メモリの許す限りフィボナッチ数列を生成することができます。
それでは実行してみましょう。
scala> var d = fibgen(0, 1)
var d: lazylist.LazyList[BigInt] = Cons(0, ?)
scala> var n = 0
var n: Int = 0
scala> while (n < 20) { println(d.car); d = d.cdr; n += 1 }
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
次は遅延ストリームを操作するメソッドを作りましょう。最初は n 番目の要素を求めるメソッド apply です。本稿では Scala のリストに合わせて先頭の要素を 0 番目とします。
リスト : n 番目の要素を求める
def apply(n: Int): A = {
var i = 0
var xs = this
while (i < n) {
xs = xs.cdr
i += 1
}
xs.car
}
変数 xs にストリーム (this) をセットします。xs.cdr で次のストリームを生成し、それを n 回繰り返すことで n 番目の要素を求めます。while ループが終了したら、xs.car でストリームの要素を取り出せばいいわけです。
ストリームから n 個の要素を取り出してリストに格納して返す関数 take も同様にプログラムすることができます。
リスト : n 個の要素を取り出す
def take(n: Int): List[A] = {
var i = 0
var xs = this
var ys: List[A] = Nil
while(i < n) {
ys = xs.car :: ys
xs = xs.cdr
i += 1
}
ys.reverse
}
変数 xs にストリーム (this) をセットし、ストリームの要素を変数 ys のリストに格納します。whileループで、xs.car を ys にプッシュして、xs を xs.cdr に書き換えます。これを n 回繰り返して、while ループを終了したら ys.reverse を返します。
ストリームから n 個の要素を取り除くメソッド drop も簡単です。
リスト : n 個の要素を取り除く
def drop(n: Int): LazyList[A] = {
var i = 0
var xs = this
while (i < n) {
xs = xs.cdr
i += 1
}
xs
}
変数 xs にストリーム (this) をセットします。whileループの中で、xs を xs.cdr に書き換えます。これを n 回繰り返して、while ループを終了したら xs を返します。
それでは、簡単な実行例を示しましょう。
scala> val s = fibgen(0, 1) val s: lazylist.LazyList[BigInt] = Cons(0, ?) scala> s(0) val res4: BigInt = 0 scala> s(10) val res5: BigInt = 55 scala> s(100) val res6: BigInt = 354224848179261915075 scala> s.take(10) val res7: List[BigInt] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34) scala> val s1 = s.drop(50) val s1: lazylist.LazyList[BigInt] = Cons(12586269025, ?) scala> s1.take(10) val res8: List[BigInt] = List(12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041)
変数 s にフィボナッチ数列を生成するストリームをセットします。s(0), s(10), s(100) で 0, 10, 100 番目の値を求めることができます。take で 10 個の要素を取り出すと、リストの要素はフィボナッチ数列になります。drop で 50 個の要素を取り除いて変数 s1 にセットします。s1,take(10) で 50 番目から 10 個の要素を取り出すことができます。
ところで、遅延ストリームは高階関数も定義することができます。次のリストを見てください。
リスト : 高階関数
// マッピング
def map[B](f: A => B): LazyList[B] =
if (isEmpty) Nils
else Cons(f(car), cdr.map(f))
// フィルター
def filter(f: A => Boolean): LazyList[A] =
if (isEmpty) Nils
else if (f(car)) Cons(car, cdr.filter(f))
else cdr.filter(f)
// 畳み込み
def foldl[B](a: B)(f: (B, A) => B): B =
if (isEmpty) a
else cdr.foldl(f(a, car))(f)
def foldr[B](a: B)(f: (A, B) => B): B =
if (isEmpty) a
else f(car, cdr.foldr(a)(f))
map と filter は関数を受け取り、新しい遅延ストリームを生成して返します。map はストリームの要素 car に関数 f を適用した結果を新しいストリームに格納して返します。filter は述語 f が真を返す要素だけを新しいストリームに格納して返します。foldl と foldr は遅延ストリームに対して畳み込み処理を行います。無限ストリームの場合は処理が終了しないので注意してください。
簡単な実行例を示しましょう。
scala> val s2 = intgen(1, 100) val s2: lazylist.LazyList[Int] = Cons(1, ?) scala> val s3 = s2.map(x => x * x) val s3: lazylist.LazyList[Int] = Cons(1, ?) scala> s3.take(10) val res9: List[Int] = List(1, 4, 9, 16, 25, 36, 49, 64, 81, 100) scala> val s4 = s2.filter(_ % 2 == 0) val s4: lazylist.LazyList[Int] = Cons(2, ?) scala> s4.take(10) val res10: List[Int] = List(2, 4, 6, 8, 10, 12, 14, 16, 18, 20) scala> s2.foldl(0)(_ + _) val res11: Int = 5050 scala> s2.foldr(0)(_ + _) val res12: Int = 5050
変数 s2 に 1 から始まる整数列を生成する遅延ストリームをセットします。次に、s2 の要素を 2 乗する遅延ストリームを map で生成して変数 s3 にセットします。take で s3 から要素を 10 個取り出すと、s2 の要素を 2 乗した値になります。
s2 から偶数列の遅延ストリームを得るには、引数が偶数のときに真を返す述語を filter に渡します。その返り値を変数 s4 にセットして、take で 10 個の要素を取り出すと、リストの要素は 2 から 20 までの値になります。
s2 は有限個の遅延ストリームなので畳み込みを行うことができます。foldl と foldr で要素の合計値を求めると 5050 になります。
次は、用意しておくと便利な高階関数を作ります。
リスト : 高階関数 (foreach, takeWhile, dropWhile)
def foreach(f: A => Unit): Unit = {
var xs = this
while (!xs.isEmpty) {
f(xs.car)
xs = xs.cdr
}
}
def takeWhile(f: A => Boolean): List[A] = {
var xs = this
var ys: List[A] = Nil
while (!xs.isEmpty && f(xs.car)) {
ys = xs.car :: ys
xs = xs.cdr
}
ys.reverse
}
def dropWhile(f: A => Boolean): LazyList[A] = {
var xs = this
while (!xs.isEmpty && f(xs.car)) xs = xs.cdr
xs
}
foreach はお馴染みのメソッドですね。無限ストリームに foreach を適用すると止まらないので注意してください。takeWhile は先頭から要素を順番に取り出してリストに格納していきますが、引数の述語 f が偽を返す要素で停止して、要素を格納したリストを返します。dropWhile は先頭から要素を順番に取り除いていきますが、引数の述語 f が偽を返す要素で停止して、その時点のストリームを返します。
簡単な例を示しましょう。
scala> val s = intgen(1, 10) val s: lazylist.LazyList[Int] = Cons(1, ?) scala> s.foreach(println) 1 2 3 4 5 6 7 8 9 10 scala> s.takeWhile(_ < 5) val res14: List[Int] = List(1, 2, 3, 4) scala> val s1 = s.dropWhile(_ < 5) val s1: lazylist.LazyList[Int] = Cons(5, ?) scala> for (x <- s1) println(x) 5 6 7 8 9 10
メソッド foreach が定義されているので、for 式で遅延ストリームから要素を順番に取り出すことができます。
次は、2 つの遅延ストリームを受け取って 1 つの遅延ストリームを返す関数を考えます。一番簡単な操作は 2 つの遅延ストリームを結合することです。次のリストを見てください。
リスト : 遅延ストリームの結合
def append[B >: A](xs: LazyList[B]): LazyList[B] =
if (isEmpty) xs
else Cons(car, cdr.append(xs))
メソッド append はストリーム this と xs を結合したストリームを返します。処理は簡単で、this の要素を順番に取り出していき、this が空になったら xs を返すだけです。
簡単な実行例を示しましょう。
scala> val s1 = intgen(1, 4) val s1: lazylist.LazyList[Int] = Cons(1, ?) scala> val s2 = intgen(5, 8) val s2: lazylist.LazyList[Int] = Cons(5, ?) scala> val s3 = s1.append(s2) val s3: lazylist.LazyList[Int] = Cons(1, ?) scala> s3.take(8) val res16: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8)
次は遅延ストリーム s1 と s2 の要素を交互に出力するストリームを作ります。次のリストを見てください。
リスト : 遅延ストリームの要素を交互に出力
def interleave[B >: A](xs: LazyList[B]): LazyList[B] =
if (isEmpty) xs
else Cons(car, xs.interleave(cdr))
メソッド interleave はストリーム this の要素を新しい遅延ストリームに格納したら、次は xs の要素を新しい遅延ストリームに格納します。これは Cons の第 2 引数で interleave を呼び出すとき、this と xs の順番を交換するだけです。このとき、this は cdr で次の要素を求めます。これで 2 つのストリームの要素を交互に出力することができます。
簡単な実行例を示しましょう。
scala> val s4 = s1.interleave(s2) val s4: lazylist.LazyList[Int] = Cons(1, ?) scala> s4.take(8) val res17: List[Int] = List(1, 5, 2, 6, 3, 7, 4, 8)
append の場合、無限ストリームを結合することはできませんが、interleave ならば無限ストリームにも対応することができます。
簡単な例を示しましょう。
scala> val ones: LazyList[Int] = Cons(1, ones) val ones: lazylist.LazyList[Int] = Cons(1, ?) scala> ones.take(20) val res18: List[Int] = List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1) scala> val twos: LazyList[Int] = Cons(2, twos) val twos: lazylist.LazyList[Int] = Cons(2, ?) scala> twos.take(20) val res19: List[Int] = List(2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2) scala> ones.interleave(twos).take(20) val res20: List[Int] = List(1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2)
ones は 1 を無限に出力するストリームで、twos は 2 を無限に出力するストリームです。append で ones と twos を結合しても無限に 1 を出力するだけですが、interleave で ones と twos を結合すれば、1 と 2 を交互に出力することができます。
遅延ストリームを操作する場合、2 つの遅延ストリームの要素に関数を適用するマップ関数 zipWith があると便利です。プログラムは次のようになります。
リスト : マップ関数
def zipWith[B, C](xs: LazyList[B])(f: (A, B) => C): LazyList[C] =
if (isEmpty || xs.isEmpty) Nils
else Cons(f(car, xs.car), cdr.zipWith(xs.cdr)(f))
ストリーム this と xs からそれぞれの要素を取り出して関数 f に渡します。そして、その評価結果を遅延ストリームに格納して返します。どちらかのストリームが空になったら Nils を返します。
簡単な実行例を示しましょう。
scala> val s1 = intgen(1, 10) val s1: lazylist.LazyList[Int] = Cons(1, ?) scala> val s2 = intgen(11, 20) val s2: lazylist.LazyList[Int] = Cons(11, ?) scala> val s3 = s1.zipWith(s2)(_ + _) val s3: lazylist.LazyList[Int] = Cons(12, ?) scala> s3.take(10) val res21: List[Int] = List(12, 14, 16, 18, 20, 22, 24, 26, 28, 30)
zipWith を使うと、遅延ストリームに対していろいろな処理を定義することができます。次の例を見てください。
scala> def streamAdd(s1: LazyList[Int], s2: LazyList[Int]): LazyList[Int] =
| s1.zipWith(s2)(_ + _)
def streamAdd(s1: lazylist.LazyList[Int], s2: lazylist.LazyList[Int]): lazylist.LazyList[Int]
scala> streamAdd(intgen(1, 100), intgen(101, 200)).take(10)
val res22: List[Int] = List(102, 104, 106, 108, 110, 112, 114, 116, 118, 120)
streamAdd は s1 と s2 の要素を加算した遅延ストリームを返します。この streamAdd を使うと、整数を生成する遅延ストリームは次のように定義することができます。
scala> val ones: LazyList[Int] = Cons(1, ones) val ones: lazylist.LazyList[Int] = Cons(1, ?) scala> val ints: LazyList[Int] = Cons(1, streamAdd(ones, ints)) val ints: lazylist.LazyList[Int] = Cons(1, ?) scala> ints.take(20) val res23: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20) scala> val fibs: LazyList[Int] = Cons(0, Cons(1, streamAdd(fibs.cdr, fibs))) val fibs: lazylist.LazyList[Int] = Cons(0, ?) scala> fibs.take(20) val res24: List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181)
ストリーム ints は、現在の ints に 1 を足し算することで整数を生成しています。fibs は現在のフィボナッチ数列を表していて、fibs.cdr で次の要素を求め、それらを足し算することで、その次の要素を求めています。この場合、ストリームの初期値として 2 つの要素が必要になることに注意してください。
それでは簡単な例題として、2 つのストリームからその要素の組み合わせを生成するストリームを作りましょう。要素が n 個のストリームの場合、組み合わせは n * n 個あります。次の図を見てください。
(a0, b0) (a0, b1) (a0, b2) ... (a0, bn)
(a1, b0) (a1, b1) (a1, b2) ... (a1, bn)
(a2, b0) (a2, b1) (a2, b2) ... (a2, bn)
...
(an, b0) (an, b1) (an, b2) ... (an, bn)
図 : n * n 個の組
この組み合わせを生成するストリームは簡単にプログラムできるように思います。次のリストを見てください。
リスト : 組を生成するストリーム
object LazyList {
def streamPair[A, B](s1: LazyList[A], s2: LazyList[B]): LazyList[(A, B)] =
if (s1.isEmpty) Nils
else s2.map(x => (s1.car, x)).append(streamPair(s1.cdr, s2))
}
関数 streamPair はストリーム s1 と s2 の要素の組を出力します。最初に、s1 の先頭要素を取り出して、map で s2 の要素との組を生成します。それを append で出力してから、streamPair を再帰呼び出しして s1 の次の要素と s2 の組を求めます。とても簡単なプログラムですが、実は重大な欠点があります。これはあとで説明します。
それでは実際に実行してみましょう。
scala> import lazylist._ import lazylist._ scala> import LazyList._ import LazyList._ scala> val s1 = streamPair(intgen(1, 4), intgen(5, 8)) val s1: lazylist.LazyList[(Int, Int)] = Cons((1,5), ?) scala> s1.take(16) val res0: List[(Int, Int)] = List((1,5), (1,6), (1,7), (1,8), (2,5), (2,6), (2,7), (2,8), (3,5), (3,6), (3,7), (3,8), (4,5), (4,6), (4,7), (4,8))
正常に動作しているように見えますが、実は遅延ストリームとしては機能していないのです。map に渡す匿名関数で生成した組を表示すると、次のようになります。
scala> val s1 = streamPair(intgen(1, 4), intgen(5, 8)) (1,5) (2,5) (3,5) (4,5) val s1: lazylist.LazyList[(Int, Int)] = Cons((1,5), ?) scala> s1.take(16) (1,6) (1,7) (1,8) (2,6) (2,7) (2,8) (3,6) (3,7) (3,8) (4,6) (4,7) (4,8) val res0: List[(Int, Int)] = List((1,5), (1,6), (1,7), (1,8), (2,5), (2,6), (2,7), (2,8), (3,5), (3,6), (3,7), (3,8), (4,5), (4,6), (4,7), (4,8))
最初に 4 つの組が生成されています。これは append の第 2 引数で streamPair を呼び出ししているために起こります。Scala の関数は「値呼び」なので、引数は必ず評価されます。したがって、append を評価する前に map と streamPair が評価され、s1 の要素 1, 2, 3, 4 に対応するストリームが生成されるのです。
このような場合、append の引数を遅延評価するとうまくいきます。次のリストを見てください。
リスト : ストリームの結合 (遅延評価版)
def appendDelay[B >: A](xs: => LazyList[B]): LazyList[B] =
if (isEmpty) xs
else Cons(car, cdr.appendDelay(xs))
関数 appendDelay の引数 s2 を名前渡しパラメータに設定するだけです。
次は streamPair を修正します。
リスト : 組を生成するストリーム
def streamPair1[A, B](s1: LazyList[A], s2: LazyList[B]): LazyList[(A, B)] =
if (s1.isEmpty) Nils
else s2.map(x => (s1.car, x)).appendDelay(streamPair1(s1.cdr, s2))
append のかわりに appendDelay を使うだけです。プログラムの修正はこれだけです。
それでは実行してみましょう。なお、動作を確認するため、生成した組を表示するようにプログラムを修正しています。
scala> val s1 = streamPair1(intgen(1, 4), intgen(5, 8)) (1,5) val s1: lazylist.LazyList[(Int, Int)] = Cons((1,5), ?) scala> s1.take(16) (1,6) (1,7) (1,8) (2,5) (2,6) (2,7) (2,8) (3,5) (3,6) (3,7) (3,8) (4,5) (4,6) (4,7) (4,8) val res0: List[(Int, Int)] = List((1,5), (1,6), (1,7), (1,8), (2,5), (2,6), (2,7), (2,8), (3,5), (3,6), (3,7), (3,8), (4,5), (4,6), (4,7), (4,8))正常に動作していますね。
ところで、streamPair は無限ストリームに対応していません。実際、引数 s2 に無限ストリームを渡した場合、引数 s1 の最初の要素を a0 とすると (a0, s2 の要素) という組しか生成されません。そこで、下図に示すように、対角線上に組を生成していくことにします。
| a0 a1 a2 a3 a4 a5 ---+----------------------------- b0 | 0 1 3 6 10 15 ... | b1 | 2 4 7 11 16 ... | b2 | 5 8 12 17 ... | b3 | 9 13 18 ... | b4 | 14 19 ... | b5 | 20 ... | | ... | 図 : 無限ストリームによる組の生成
図を見ればおわかりのように、対角線の要素数を n とすると、組は (an-1, b0), (an-2, b1), ..., (a1, bn-2), (a0, bn-1) となっています。これは、s1 から n 個の要素を取り出したリストと、s2 から n 個の要素を取り出して反転したリストを、zip でまとめた形になっています。これをプログラムすると次のようになります。
リスト : 無限ストリームによる組の生成
def streamOfList[A](xs: List[A]): LazyList[A] =
xs match {
case Nil => Nils
case (y::ys) => Cons(y, streamOfList(ys))
}
def streamPair2[A, B](s1: LazyList[A], s2: LazyList[B]): LazyList[(A, B)] = {
def iter(n: Int): LazyList[(A, B)] =
streamOfList(s1.take(n).zip(s2.take(n).reverse)).appendDelay(iter(n + 1))
iter(1)
}
実際の処理は局所関数 iter で行っています。引数 n が対角線上の要素数を表します。take で s1 と s2 から要素を取り出し、s2 から取り出したリストを reverse で反転してから zip でタプルに格納します。結果はリストになるので、streamOfList でリストを遅延ストリームに変換します。そして、そのストリームと再帰呼び出しした iter の返り値を appendDelay で連結します。これで組を対角線上の順番で生成することができます。
それでは実行してみましょう。
scala> def from(n: Int): LazyList[Int] = Cons(n, from(n + 1)) def from(n: Int): lazylist.LazyList[Int] scala> val s = streamPair2(from(1), from(1)) val s: lazylist.LazyList[(Int, Int)] = Cons((1,1), ?) scala> s.take(50) val res1: List[(Int, Int)] = List((1,1), (1,2), (2,1), (1,3), (2,2), (3,1), (1,4), (2,3), (3,2), (4,1), (1,5), (2,4), (3,3), (4,2), (5,1), (1,6), (2,5), (3,4), (4,3), (5,2), (6,1), (1,7), (2,6), (3,5), (4,4), (5,3), (6,2), (7,1), (1,8), (2,7), (3,6), (4,5), (5,4), (6,3), (7,2), (8,1), (1,9), (2,8), (3,7), (4,6), (5,5), (6,4), (7,3), (8,2), (9,1), (1,10), (2,9), (3,8), (4,7), (5,6)) scala> s(25) val res2: (Int, Int) = (5,3) scala> s(49) val res3: (Int, Int) = (5,6)
正常に動作していますね。
次は無限の素数列を生成するプログラムを作ってみましょう。整数 n が素数か確かめる簡単な方法は、√n 以下の素数で割り切れるか試してみることです。割り切れる素数があれば、n は素数ではありません。そうでなければ、n は素数であることがわかります。
これをそのままプログラムすると次のようになります。
リスト : 素数列の生成
def checkPrime(n: Int): Boolean =
primes.takeWhile(x => x * x <= n).forall(n % _ != 0)
def primesFrom(n: Int): LazyList[Int] =
if (checkPrime(n)) Cons(n, primesFrom(n + 2))
else primesFrom(n + 2)
val primes: LazyList[Int] = Cons(2, Cons(3, Cons(5, primesFrom(7))))
変数 primes は無限の素数列を表します。実際に素数を生成する処理は関数 primesFrom で行います。primesFrom は簡単で、関数 checkPrime を呼び出して n が素数かチェックします。そうであれば、n を遅延ストリームに追加します。そうでなければ primesFrom を再帰呼び出しするだけです。偶数は素数ではないので、引数 n には奇数を与えていることに注意してください。
checkPrime も簡単です。takeWhile で primes から √n 以下の素数列を取り出します。√n 以下の素数は生成済みなので、primes から takeWhile で取り出すことが可能です。ここでは√n のかわりに条件を x * x <= n としています。あとは、関数 forall を使って、取り出した素数で n が割り切れないことを確認するだけです。
それでは実行してみましょう。
scala> primes.take(25) val res4: List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97) scala> primes(99) val res5: Int = 541 scala> primes(500) val res6: Int = 3581
100 以下の素数は全部で 25 個あります。また、100 番目の素数は 541 になります。Scala のリストは 0 から数えるので、primes(99) で 100 番目の素数になります。
もうひとつ素数列を生成する簡単な方法を紹介しましょう。考え方は簡単です。最初に、2 から始まる整数列を生成するストリームを用意します。2 は素数なので、素数ストリームの要素になります。次に、この整数列から 2 で割り切れる整数を取り除き除きます。これは filter を使うと簡単です。
2 で割り切れる整数が取り除かれたので、次の要素は 3 になります。今度は 3 で割り切れる整数を取り除けばいいのです。これも filter を使えば簡単です。このとき、入力用のストリームは 2 で割り切れる整数が取り除かれています。したがって、このストリームに対して 3 で割り切れる整数を取り除くように filter を設定すればいいわけです。
このように、素数を見つけたらそれで割り切れる整数を取り除いていくアルゴリズムを「エラトステネスの篩」といいます。ようするに、2 から始まる整数ストリームに対して、見つけた素数 2, 3, 5, 7, 11, ... を順番に fiter で設定して素数でない整数をふるい落としていくわけです。
プログラムは次のようになります。
リスト : 素数列の生成
def from(n: Int): LazyList[Int] = Cons(n, from(n + 1))
def sieve(s: LazyList[Int]): LazyList[Int] =
Cons(s.car, sieve(s.cdr.filter(_ % s.car != 0)))
関数 from は n から始まる整数列を生成します。関数 sieve には 2 から始まる整数列を生成するストリームを渡します。Cons の第 2 引数を評価すると、filter により整数列から 2 で割り切れる整数を取り除いたストリームが返されます。次の要素 3 を取り出すとき、このストリームに対して 3 で割り切れる整数を取り除くことになるので、2 と 3 で割り切れる整数が取り除かれることになります。次の要素は 5 になりますが、そのストリームからさらに 5 で割り切れる整数が filter で取り除かれることになります。
このように filter を重ねて設定していくことで、素数でない整数をふるい落としていくことができるわけです。それでは実行してみましょう。
scala> val s = sieve(from(2)) val s: lazylist.LazyList[Int] = Cons(2, ?) scala> s.take(25) val res7: List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97) scala> s(500) val res8: Int = 3581
正常に動作していますね。
最後に、Scala の遅延ストリーム LazyList の使い方を簡単に説明します。
今回作成した遅延ストリームは、Cons で遅延ストリームを生成するとき、ストリームの要素となる第 1 引数を評価しています。たとえば、Cons(func(x), ...) とすると、func(x) を評価した値がストリームの要素となります。ここで、ストリームにまだアクセスしていないのに、func(x) が評価されていることに注意してください。もし、func(x) がデータの入力処理だとすると、遅延ストリームを生成するときにデータをひとつ先読みしてしまうことになります。
Scala の LazyList の場合、型が LazyList[A] で、Cons に対応するのが演算子 #:: になります。このとき、#:: の左辺 (遅延ストリームの要素) も遅延評価されることに注意してください。car, cdr に対応するのがメソッド head, tail です。ストリームの終端は LazyList.empty で表します。
簡単な例を示しましょう。
scala> import scala.collection.immutable.LazyList
import scala.collection.immutable.LazyList
scala> def intgen(n: Int, m: Int): LazyList[Int] =
| if (n > m) LazyList.empty else n #:: intgen(n + 1, m)
def intgen(n: Int, m: Int): scala.collection.immutable.LazyList[Int]
scala> val s = intgen(1, 10)
val s: scala.collection.immutable.LazyList[Int] = LazyList(<not computed>)
scala> s.head
val res0: Int = 1
scala> s.tail.head
val res1: Int = 2
scala> s.tail.tail.head
val res2: Int = 3
scala> s
val res3: scala.collection.immutable.LazyList[Int] = LazyList(1, 2, 3, <not computed>)
scala> s(0)
val res4: Int = 1
scala> s(3)
val res5: Int = 4
ストリームの連結は演算子 ++ で行うことができます。
scala> val a = intgen(1, 4) val a: scala.collection.immutable.LazyList[Int] = LazyList(<not computed>) scala> val b = intgen(5, 8) val b: scala.collection.immutable.LazyList[Int] = LazyList(<not computed>) scala> val c = a ++ b val c: scala.collection.immutable.LazyList[Int] = LazyList(<not computed>) scala> c.foreach(println) 1 2 3 4 5 6 7 8
LazyList のメソッド take, takeWhile はリストではなく有限の LazyList を返すことに注意してください。
scala> val d = intgen(1, 100) val d: scala.collection.immutable.LazyList[Int] = LazyList(<not computed>) scala> d.take(10) val res7: scala.collection.immutable.LazyList[Int] = LazyList(<not computed>) scala> d.take(10).toList val res8: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) scala> d.take(10).foreach(println) 1 2 3 4 5 6 7 8 9 10 scala> d.takeWhile(_ < 10).toList val res10: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
メソッド zip は LazyList に用意されていますが zipWith はありません。zip と map を組み合わせて使うことになります。
scala> val ones: LazyList[Int] = 1 #:: ones val ones: scala.collection.immutable.LazyList[Int] = LazyList(<not computed>) scala> val ints: LazyList[Int] = 1 #:: ones.zip(ints).map(x => x._1 + x._2) val ints: scala.collection.immutable.LazyList[Int] = LazyList(<not computed>) scala> ints.take(10).toList val res11: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) scala> val fibs: LazyList[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map(x => x._1 + x._2) val fibs: scala.collection.immutable.LazyList[BigInt] = LazyList(<not computed>) scala> fibs.take(10).toList val res12: List[BigInt] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34) scala> fibs(50) val res13: BigInt = 12586269025 scala> fibs(100) val res14: BigInt = 354224848179261915075
最後にエラトステネスの篩を示します。
scala> def sieve(s: LazyList[Int]): LazyList[Int] = s.head #:: sieve(s.tail.filter(_ % s.head != 0)) def sieve(s: scala.collection.immutable.LazyList[Int]): scala.collection.immutable.LazyList[Int] scala> val primes = sieve(ints.tail) val primes: scala.collection.immutable.LazyList[Int] = LazyList(<not computed>) scala> primes.take(25).toList val res15: List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97) scala> primes(500) val res16: Int = 3581
このほかにも LazyList には多数のメソッドや演算子が用意されています。興味のある方はリファレンス scala.collection.immutable.LazyList をお読みくださいませ。
//
// lazylist.scala : シンプルな遅延ストリーム
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
package lazylist
// 遅延ストリーム (抽象クラス)
abstract class LazyList[+A] {
def car: A
def cdr: LazyList[A]
def isEmpty: Boolean
def apply(n: Int): A = {
var i = 0
var xs = this
while (i < n) {
xs = xs.cdr
i += 1
}
xs.car
}
def take(n: Int): List[A] = {
var i = 0
var xs = this
var ys: List[A] = Nil
while(i < n) {
ys = xs.car :: ys
xs = xs.cdr
i += 1
}
ys.reverse
}
def drop(n: Int): LazyList[A] = {
var i = 0
var xs = this
while (i < n) {
xs = xs.cdr
i += 1
}
xs
}
// 高階関数
def map[B](f: A => B): LazyList[B] =
if (isEmpty) Nils
else Cons(f(car), cdr.map(f))
def filter(f: A => Boolean): LazyList[A] =
if (isEmpty) Nils
else if (f(car)) Cons(car, cdr.filter(f))
else cdr.filter(f)
def foldl[B](a: B)(f: (B, A) => B): B =
if (isEmpty) a
else cdr.foldl(f(a, car))(f)
def foldr[B](a: B)(f: (A, B) => B): B =
if (isEmpty) a
else f(car, cdr.foldr(a)(f))
def foreach(f: A => Unit): Unit = {
var xs = this
while (!xs.isEmpty) {
f(xs.car)
xs = xs.cdr
}
}
def takeWhile(f: A => Boolean): List[A] = {
var xs = this
var ys: List[A] = Nil
while (!xs.isEmpty && f(xs.car)) {
ys = xs.car :: ys
xs = xs.cdr
}
ys.reverse
}
def dropWhile(f: A => Boolean): LazyList[A] = {
var xs = this
while (!xs.isEmpty && f(xs.car)) xs = xs.cdr
xs
}
// ストリームの連結
def append[B >: A](xs: LazyList[B]): LazyList[B] =
if (isEmpty) xs
else Cons(car, cdr.append(xs))
// 遅延評価版
def appendDelay[B >: A](xs: => LazyList[B]): LazyList[B] =
if (isEmpty) xs
else Cons(car, cdr.appendDelay(xs))
// ストリームの要素を交互に出力
def interleave[B >: A](xs: LazyList[B]): LazyList[B] =
if (isEmpty) xs
else Cons(car, xs.interleave(cdr))
// 2 つのストリームの要素をタプルにまとめる
def zip[B](xs: LazyList[B]): LazyList[(A, B)] =
if (isEmpty || xs.isEmpty) Nils
else Cons((car, xs.car), cdr.zip(xs.cdr))
// zip + map
def zipWith[B, C](xs: LazyList[B])(f: (A, B) => C): LazyList[C] =
if (isEmpty || xs.isEmpty) Nils
else Cons(f(car, xs.car), cdr.zipWith(xs.cdr)(f))
}
// セル
class Cons[A] private (a: A, b: => LazyList[A]) extends LazyList[A] {
lazy val c = b
def car: A = a
def cdr: LazyList[A] = c
def isEmpty: Boolean = false
override def toString: String = "Cons(" + a + ", ?)"
}
object Cons {
def apply[A](a: A, b: => LazyList[A]) = new Cons(a, b)
}
// 終端
case object Nils extends LazyList[Nothing] {
def car = throw new Exception("Empty LazyList")
def cdr = throw new Exception("Empty LazyList")
def isEmpty: Boolean = true
}
object LazyList {
// 整数列の生成
def intgen(n: Int, m: Int): LazyList[Int] =
if (n > m) Nils else Cons(n, intgen(n + 1, m))
def from(n: Int): LazyList[Int] = Cons(n, from(n + 1))
// 組の生成
def streamPair[A, B](s1: LazyList[A], s2: LazyList[B]): LazyList[(A, B)] =
if (s1.isEmpty) Nils
else s2.map(x => (s1.car, x)).append(streamPair(s1.cdr, s2))
def streamPair1[A, B](s1: LazyList[A], s2: LazyList[B]): LazyList[(A, B)] =
if (s1.isEmpty) Nils
else s2.map(x => (s1.car, x)).appendDelay(streamPair1(s1.cdr, s2))
def streamPair2[A, B](s1: LazyList[A], s2: LazyList[B]): LazyList[(A, B)] = {
def iter(n: Int): LazyList[(A, B)] =
streamOfList(s1.take(n).zip(s2.take(n).reverse)).appendDelay(iter(n + 1))
iter(1)
}
// リストを遅延ストリームに変換
def streamOfList[A](xs: List[A]): LazyList[A] =
xs match {
case Nil => Nils
case (y::ys) => Cons(y, streamOfList(ys))
}
// 素数列の生成
def checkPrime(n: Int): Boolean =
primes.takeWhile(x => x * x <= n).forall(n % _ != 0)
def primesFrom(n: Int): LazyList[Int] =
if (checkPrime(n)) Cons(n, primesFrom(n + 2))
else primesFrom(n + 2)
val primes: LazyList[Int] = Cons(2, Cons(3, Cons(5, primesFrom(7))))
// エラトステネスの篩
def sieve(s: LazyList[Int]): LazyList[Int] =
Cons(s.car, sieve(s.cdr.filter(_ % s.car != 0)))
}