「ストリーム (stream)」はデータの流れを抽象化したデータ構造です。たとえば、ファイル入出力はストリームと考えることができます。また、配列や連結リストを使ってストリームを表すこともできます。ただし、単純な配列や連結リストでは、有限個のデータの流れしか表すことができません。ところが、遅延評価を用いると擬似的に無限個のデータを表すことができるようになります。これを「遅延ストリーム」とか「遅延リスト」と呼びます。
Java の Stream は遅延ストリームですが immutable ではありません。前回作成したクラス Delay<T> を使うと、完全ではありませんが関数型言語のような immutable な遅延ストリームを作ることができます。Java で immutable な遅延ストリームを使うことはほとんどないでしょうが、今回は Java のお勉強ということで、実際にプログラムを作ってみましょう。
遅延ストリームの基本的な考え方は、必要になったときに新しいデータを生成することです。このときに遅延評価を用います。具体的にはデータを生成するメソッドを用意し、それを遅延評価してストリームに格納しておきます。そして、必要になった時点で遅延評価しておいたメソッドを呼び出して値を求めればよいわけです。
今回作成する遅延ストリームはクラス名を LazyStream<E> とし、パッケージ immutable 内に定義することにします。プログラムは次のようになります。
リスト : 遅延ストリーム
package immutable;
import java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.function.BiFunction;
import immutable.Delay;
import immutable.ImList;
public final class LazyStream<E> {
private final E item;
private final Delay<LazyStream<E>> next;
private LazyStream(E x, Supplier<LazyStream<E>> func) {
item = x;
next = Delay.delay(func);
}
// 終端
private final static LazyStream<?> NIL = new LazyStream<>(null, null);
public static <E> LazyStream<E> nil() {
@SuppressWarnings("unchecked")
LazyStream<E> t = (LazyStream<E>)NIL;
return t;
}
public boolean isEmpty() { return this == NIL; }
// メソッドの定義
・・・省略・・・
}
フィールド変数 item に先頭の要素を格納し、next に遅延ストリームを生成する Delay<LazyStream<E>> を格納します。これを force() することで、次の要素を格納した遅延ストリームを生成します。スタティック変数 NIL は遅延ストリームの終端 (空の遅延ストリーム) を表します。スタティックメソッド nil() は空の遅延ストリームを返し、メソッド isEmpty() は遅延ストリームが空であれば真を返します。
次は遅延ストリームを操作する基本的なメソッドを定義します。
リスト : 遅延ストリームの基本的な操作メソッド
// 遅延ストリームの生成
public static <E> LazyStream<E> cons(E x, Supplier<LazyStream<E>> func) {
return new LazyStream<E>(x, func);
}
// 先頭要素を取り出す
public E first() {
if (this == NIL)
throw new IndexOutOfBoundsException("LazyStream.first()");
return item;
}
// 先頭要素を取り除く
public LazyStream<E> rest() {
if (this == NIL)
throw new IndexOutOfBoundsException("LazyStream.rest()");
return next.force();
}
スタティックメソッド cons() は、先頭要素が x の遅延ストリームを生成します。メソッド first() は遅延ストリームから要素を取り出して返します。メソッド rest() は遅延ストリームのフィールド変数 next を force() して、次の要素を格納した遅延ストリームを生成します。ようするに、これらのメソッドは連結リスト ImList のメソッド cons(), first(), rest() に、Lisp / Scheme でいえばリスト操作関数 cons, car, cdr に対応しているわけです。
それでは、遅延ストリームを生成するスタティックメソッドを作りましょう。たとえば、low 以上 high 以下の整数列を生成する遅延ストリームは次のようにプログラムすることができます。
リスト : 整数列を生成する遅延ストリーム
public static LazyStream<Integer> iota(int low, int high) {
if (low > high)
return nil();
else
return cons(low, () -> iota(low + 1, high));
}
メソッド iota() は遅延ストリームを生成して返します。cons() の第 1 引数が現時点でのデータになります。第 2 引数にはラムダ式を渡して、その中で iota() を呼び出します。rest() を実行すると、遅延オブジェクトに格納されたラムダ式が評価され、その本体である iota() が実行されて次のデータを格納した遅延ストリームが返されます。その遅延ストリームに対してさらに rest() を実行すると、その次のデータを得ることができます。
簡単な例を示しましょう。
jshell> import immutable.LazyStream
jshell> var xs0 = LazyStream.iota(1, 10)
xs0 ==> immutable.LazyStream@1a86f2f1
jshell> xs0.first()
$3 ==> 1
jshell> xs0.rest().first()
$4 ==> 2
jshell> xs0.rest().rest().first()
$5 ==> 3
jshell> var xs1 = xs0
xs1 ==> immutable.LazyStream@1a86f2f1
jshell> while (!xs1.isEmpty()) { System.out.println(xs1.first()); xs1 = xs1.rest(); }
1
2
3
4
5
6
7
8
9
10
jshell> xs0.first()
$8 ==> 1
jshell> xs0.rest().first()
$9 ==> 2
jshell> xs0.rest().rest().first()
$10 ==> 3
遅延ストリーム xs0 に rest() を適用することで、次々とデータを生成することができます。また、while ループの中で変数 xs1 の値を書き換えれば、遅延ストリームの要素を順番に取り出していくことができます。このとき、遅延ストリーム自体の値は書き換えられていないことに注意してください。xs0 の値を書き換えない限り、xs0.first() の値は 1 で、xs0.rest().first() の値は 2 のままです。
次は無限ストリームを生成するスタティックメソッドを作りましょう。次のリストを見てください。
リスト : 無限ストリームの生成
// x を繰り返し出力する
public static <E> LazyStream<E> repeat(E x) {
return cons(x, () -> repeat(x));
}
// メソッド func が生成する値を遅延ストリームに格納する
public static <E> LazyStream<E> generate(Supplier<E> func) {
return cons(func.get(), () -> generate(func));
}
// 前項にメソッドを適用して次項を生成する
public static <E> LazyStream<E> iterate(E a, Function<E, E> func) {
return cons(a, () -> iterate(func.apply(a), func));
}
メソッド repeat() は引数 x を無限に出力する遅延ストリームを生成します。cons() の第 1 引数に x を渡して、第 2 引数のラムダ式で repeat(x) を呼び出すだけです。メソッド generate() は引数のメソッド func が生成する値を遅延ストリームに格納します。cons() の第 1 引数に func.get() の返り値を渡して、ラムダ式で generate(func) を呼び出すだけです。
メソッド iterate() は第 1 引数に初項を指定して、第 2 引数のメソッドで前項から次項を生成します。これは cons() の第 1 引数に a を渡して、ラムダ式の中で iterate() の第 1 引数に func.apply(a) の返り値をセットするだけです。これで、引数 a の値から次項の値を求めることができます。
簡単な実行例を示しましょう。
jshell> var xs = LazyStream.repeat(1)
xs ==> immutable.LazyStream@531d72ca
jshell> for (int i = 0; i < 16; i++) { System.out.print(xs.first() + " "); xs = xs.rest(); }
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
jshell> var ys = LazyStream.iterate(1, x -> x + 2)
ys ==> immutable.LazyStream@4b9af9a9
jshell> for (int i = 0; i < 16; i++) { System.out.print(ys.first() + " "); ys = ys.rest(); }
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
repeat(1) は無限に 1 を出力する遅延ストリームを生成します。iterate(1, x -> x + 2) は無限の奇数列を生成する遅延ストリームになります。
もう一つ、簡単な例を示しましょう。多倍長整数 (BigInteger) でフィボナッチ数列を生成する遅延ストリームを作ります。次の例を見てください。
jshell> LazyStream<BigInteger> fibonacci(BigInteger a, BigInteger b) {
...> return LazyStream.cons(a, () -> fibonacci(b, a.add(b)));
...> }
| 次を作成しました: メソッド fibonacci(BigInteger,BigInteger)
jshell> var fibo = fibonacci(BigInteger.ZERO, BigInteger.ONE)
fibo ==> immutable.LazyStream@5cb0d902
jshell> for (int i = 0; i < 50; i++) { System.out.print(fibo.first() + " "); fibo = fibo.rest(); }
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025
121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169
63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976
7778742049
メソッド fibonacci() の引数 a がフィボナッチ数列の最初の項で、b が次の項です。したがって、ラムダ式に fibonacci(b, a.add(b)) を格納しておけば、rest() を実行することでフィボナッチ数列を生成することができます。
次は遅延ストリームを操作するメソッドを作りましょう。最初は n 番目の要素を求めるメソッド get() です。
リスト : n 番目の要素を求める
public E get(int n) {
var xs = this;
while (n-- > 0) {
xs = xs.rest();
}
return xs.first();
}
get() は rest() を n 回繰り返して n 番目の要素を求めるだけです。
遅延ストリームから n 個の要素を取り出して List<E> に格納して返すメソッド take() と先頭から n 個の要素を取り除くメソッド drop() も同様にプログラムすることができます。
リスト : 要素を n 個取り出して List<E> に格納して返す
public List<E> take(int n) {
var xs = this;
var ys = new ArrayList<E>();
while (n-- > 0 && xs != NIL) {
ys.add(xs.first());
xs = xs.rest();
}
return ys;
}
リスト : 先頭から n 個要素を取り除く
public LazyStream<E> drop(int n) {
var xs = this;
while (n-- > 0 && xs != NIL) {
xs = xs.rest();
}
return xs;
}
take() は while ループで first() と rest() を n 回繰り返し、要素を ArrayList<E> に格納して返します。drop() は rest() を n 回繰り返すだけです。
簡単な実行例を示しましょう。
jshell> var fibo = fibonacci(BigInteger.ZERO, BigInteger.ONE)
fibo ==> immutable.LazyStream@4459eb14
jshell> for (int i = 0; i < 20; i++) { System.out.print(fibo.get(i) + " "); fibo = fibo.rest(); }
0 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309 5702887 14930352 39088169
jshell> var fibo = fibonacci(BigInteger.ZERO, BigInteger.ONE)
fibo ==> immutable.LazyStream@28c97a5
jshell> for (int i = 0; i < 20; i++) { System.out.print(fibo.get(i) + " "); }
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
jshell> fibo.take(20)
$28 ==> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
jshell> fibo.drop(40).take(10)
$29 ==> [102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903,
2971215073, 4807526976, 7778742049]
変数 fibo にフィボナッチ数列を生成する遅延ストリームをセットします。get() で順番に要素を 20 個取り出すと、その値はフィボナッチ数列になっていますね。take() を使うと取り出した要素を ArrayList に格納することができます。drop() で 40 個の要素を取り除き、take() で 10 個の要素を取り出します。すると、その要素は 40 番目以降のフィボナッチ数列になります。
次は、2 つの遅延ストリームを受け取って 1 つの遅延ストリームを返すメソッドを考えてみましょう。一番簡単な操作は 2 つの遅延ストリームを連結することです。次のリストを見てください。
リスト : 遅延ストリームの連結
public LazyStream<E> append(LazyStream<E> ys) {
if (this == NIL)
return ys;
else
return cons(first(), () -> rest().append(ys));
}
メソッド append() は自分 (this) と引数の遅延ストリーム xs を連結した遅延ストリームを返します。処理は簡単で、自分の要素を順番に取り出していき、空になったら ys を返すだけです。
次は 2 つの遅延ストリームの要素を交互に出力する遅延ストリームを作ります。次のリストを見てください。
リスト : 遅延ストリームの要素を交互に出力
public LazyStream<E> interleave(LazyStream<E> ys) {
if (this == NIL)
return ys;
else
return cons(first(), () -> ys.interleave(rest()));
}
メソッド interleave() は、自分の要素を新しい遅延ストリームに格納したら、次は引数 ys の要素を新しい遅延ストリームに格納します。これはラムダ式で interleave() を呼び出すとき、ys に対して interleave() を呼び出して、その引数に rest() の返り値を渡すだけです。これで要素を交互に出力することができます。
簡単な実行例を示しましょう。
jshell> var xs = LazyStream.iota(1, 8) xs ==> immutable.LazyStream@2328c243 jshell> var ys = LazyStream.iota(1, 8) ys ==> immutable.LazyStream@bebdb06 jshell> xs.append(ys).take(16) $32 ==> [1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8] jshell> var ones = LazyStream.repeat(1) ones ==> immutable.LazyStream@7591083d jshell> var twos = LazyStream.repeat(2) twos ==> immutable.LazyStream@736e9adb jshell> ones.append(twos).take(16) $35 ==> [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] jshell> ones.interleave(twos).take(16) $36 ==> [1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]
append() の場合、無限ストリーム ones と twos を連結することはできません。ones の要素である 1 をずっと出力するだけです。ところが、interleave() ならば無限ストリームにも対応することができます。ones と twos を interleave() で連結すると、1 と 2 が交互に出力されます。
次は、遅延ストリーム用の高階関数を作りましょう。
リスト : 高階関数
// マッピング
public <U> LazyStream<U> map(Function<? super E, ? extends U> func) {
if (this == NIL)
return nil();
else
return cons(func.apply(first()), () -> rest().map(func));
}
// フィルター
public LazyStream<E> filter(Predicate<E> pred) {
var xs = this;
while (xs != NIL) {
if (pred.test(xs.first())) {
LazyStream<E> ys = xs;
return cons(ys.first(), () -> ys.rest().filter(pred));
}
xs = xs.rest();
}
return nil();
}
// 畳み込み
public <U> U foldLeft(BiFunction<U, ? super E, U> func, U a) {
var xs = this;
while (xs != NIL) {
a = func.apply(a, xs.first());
xs = xs.rest();
}
return a;
}
public <U> U foldRight(BiFunction<? super E, U, U> func, U a) {
if (this == NIL)
return a;
else
return func.apply(first(), rest().foldRight(func, a));
}
// 巡回
public void forEach(Consumer<? super E> func) {
var xs = this;
while (xs != NIL) {
func.accept(xs.first());
xs = xs.rest();
}
}
map() は遅延ストリームの要素にメソッド func を適用し、その返り値を新しい遅延ストリームに格納して返します。filter() は述語 pred が真を返す要素だけを新しい遅延ストリームに格納して返します。
foldLeft() と foldRight() は遅延ストリームに対して畳み込みを行います。forEach() は遅延ストリームの要素にメソッド func を適用します。無限ストリームの場合、これらのメソッドは処理が終了しないので注意してください。
簡単な実行例を示しましょう。
jshell> import immutable.ImList jshell> var xs = LazyStream.iota(1, 20) xs ==> immutable.LazyStream@4bf558aa jshell> xs.map(x -> x * x).forEach(x -> System.out.print(x + " ")) 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 jshell> xs.filter(x -> x % 2 == 0).forEach(x -> System.out.print(x + " ")) 2 4 6 8 10 12 14 16 18 20 jshell> xs.foldLeft((a, x) -> a + x, 0) $41 ==> 210 jshell> xs.foldRight((x, a) -> a + x, 0) $42 ==> 210 jshell> xs.foldLeft((a, x) -> ImList.cons(x, a), ImList.nil()) $43 ==> (20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1) jshell> xs.foldRight((x, a) -> ImList.cons(x, a), ImList.nil()) $44 ==> (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)
変数 xs に 1 から 20 までの整数列を生成する遅延ストリームをセットします。map() にラムダ式 x -> x * x を渡すと、要素を 2 乗した遅延ストリームを生成することができます。filter() にラムダ式 x -> x % 2 == 0 を渡すと、偶数の要素を取り出すことができます。これらの遅延ストリームに forEach() を適用すると、要素を順番に取り出して出力することができます。
xs は有限個の遅延ストリームなので畳み込みを行うことができます。foldLeft() と foldRight() で要素の合計値を求めると 210 になります。連結リスト ImList<E> のメソッド cons() を適用すると、遅延ストリームの要素を連結リストに格納することができます。
次は高階関数 flatMap() を作りましょう。このとき、次のように append() を使って flatMap() を定義すると問題が発生します。
リスト : flatMap() の定義 (間違い)
public <U> LazyStream<U> flatMapBad(Function<? super E, LazyStream<U>> func) {
if (this == NIL)
return nil();
else
return func.apply(first()).append(rest().flatMapBad(func));
}
Java のメソッドは正格評価なので、append() を実行する前に引数が評価されます。つまり、flatMapBad() の評価は遅延されるのではなく、遅延ストリームが空になるまで flatMapBad() が再帰呼び出しされるのです。これでは無限ストリームに対応することができません。
そこで、引数に遅延オブジェクトを受け取るメソッド lazyAppend() を作ることにします。プログラムは次のようになります。
リスト : lazyAppend() と flatMap()
public LazyStream<E> lazyAppend(Delay<LazyStream<E>> ys) {
if (this == NIL)
return ys.force();
else
return cons(first(), () -> rest().lazyAppend(ys));
}
public <U> LazyStream<U> flatMap(Function<? super E, LazyStream<U>> func) {
if (this == NIL)
return nil();
else
return func.apply(first()).lazyAppend(Delay.delay(() -> rest().flatMap(func)));
}
lazyAppend() は append() とほぼ同じですが、遅延ストリームが空になったら遅延オブジェクト ys を force() で評価するところが異なります。flatMap() では、appned() のかわりに lazyAppend() を呼び出します。このとき、delay() で生成した遅延オブジェクトを引数に渡します。
それでは実行してみましょう。
jshell> var xs = LazyStream.iterate(1, x -> x + 1) xs ==> immutable.LazyStream@28ba21f3 jshell> xs.flatMap(x -> LazyStream.fill(x, x)).take(55) $46 ==> [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
fill(n, x) は LazyStream のスタティックメソッドで、要素 x を n 個格納した遅延ストリームを返します。xs は無限ストリームになりますが、flatMap() は正常に動作していますね。
次は、遅延ストリームの先頭から述語が真を返す要素を取り出す takeWhile() と要素を取り除く dropWhile() を作ります。
リスト : takeWhile() と dropWhile()
// 先頭から述語 pred が真を返す要素をリストに格納して返す
public List<E> takeWhile(Predicate<E> pred) {
var xs = this;
var ys = new ArrayList<E>();
while (xs != NIL && pred.test(xs.first())) {
ys.add(xs.first());
xs = xs.rest();
}
return ys;
}
// 先頭から述語 pred が真を返す要素を取り除く
public LazyStream<E> dropWhile(Predicate<E> pred) {
var xs = this;
while (xs != NIL && pred.test(xs.first())) xs = xs.rest();
return xs;
}
}
どちらのメソッドも難しいところはないと思います。簡単な実行例を示しましょう。
jshell> var xs = LazyStream.iota(1, 20) xs ==> immutable.LazyStream@2530c12 jshell> xs.takeWhile(x -> x < 10) $48 ==> [1, 2, 3, 4, 5, 6, 7, 8, 9] jshell> xs.dropWhile(x -> x < 10).forEach(System.out::println) 10 11 12 13 14 15 16 17 18 19 20
次は、コレクション List<E> と連結リスト ImList<E> を遅延ストリームに変換するスタティックメソッド of() を作ります。
リスト : スタティックメソッド of()
// ImList<E> を LazyStream<E> に変換する
public static <E> LazyStream<E> of(ImList<? extends E> xs) {
if (xs.isEmpty())
return nil();
else
return cons(xs.first(), () -> of(xs.rest()));
}
// List<E> を LazyStream<E> に変換する
private static <E> LazyStream<E> of(List<? extends E> xs, int n) {
if (n == xs.size())
return nil();
else
return cons(xs.get(n), () -> of(xs, n + 1));
}
public static <E> LazyStream<E> of(List<? extends E> xs) {
return of(xs, 0);
}
どちらのメソッドも先頭から要素を順番に取り出して、遅延ストリームに格納して返すだけです。簡単な実行例を示します。
jshell> var a = Arrays.asList(1,2,3,4,5,6,7,8)
a ==> [1, 2, 3, 4, 5, 6, 7, 8]
jshell> var xs = LazyStream.of(a)
xs ==> immutable.LazyStream@2b05039f
jshell> xs.take(8)
$52 ==> [1, 2, 3, 4, 5, 6, 7, 8]
jshell> var b = ImList.of("foo", "bar", "baz", "oops")
b ==> (foo bar baz oops)
jshell> var ys = LazyStream.of(b)
ys ==> immutable.LazyStream@4e515669
jshell> ys.forEach(System.out::println)
foo
bar
baz
oops
今回はここまでです。次回は遅延ストリームを使っていろいろなプログラムを作ってみましょう。
//
// LazyStream.java : immutable な遅延ストリーム
//
// Copyright (C) 2016-2021 Makoto Hiroi
//
package immutable;
import java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.function.BiFunction;
import immutable.Delay;
import immutable.ImList;
public final class LazyStream<E> {
private final E item;
private final Delay<LazyStream<E>> next;
private LazyStream(E x, Supplier<LazyStream<E>> func) {
item = x;
next = Delay.delay(func);
}
// 終端
private final static LazyStream<?> NIL = new LazyStream<>(null, null);
public static <E> LazyStream<E> nil() {
@SuppressWarnings("unchecked")
LazyStream<E> t = (LazyStream<E>)NIL;
return t;
}
public boolean isEmpty() { return this == NIL; }
//
// 遅延ストリームの生成
//
// 要素 x を格納した遅延ストリームを生成する
public static <E> LazyStream<E> cons(E x, Supplier<LazyStream<E>> func) {
return new LazyStream<E>(x, func);
}
// 初項を a とし、前項に func を適用して次項を生成する
public static <E> LazyStream<E> iterate(E a, Function<E, E> func) {
return cons(a, () -> iterate(func.apply(a), func));
}
// func の返り値を要素とする遅延ストリームを生成する
public static <E> LazyStream<E> generate(Supplier<E> func) {
return cons(func.get(), () -> generate(func));
}
// 要素が x の遅延ストリームを生成する
public static <E> LazyStream<E> repeat(E x) {
return cons(x, () -> repeat(x));
}
// n 個の x を格納する遅延ストリームを生成する
public static <E> LazyStream<E> fill(int n, E x) {
if (n <= 0)
return nil();
else
return cons(x, () -> fill(n - 1, x));
}
// ImList<E> を LazyStream<E> に変換する
public static <E> LazyStream<E> of(ImList<? extends E> xs) {
if (xs.isEmpty())
return nil();
else
return cons(xs.first(), () -> of(xs.rest()));
}
// List<E> を LazyStream<E> に変換する
private static <E> LazyStream<E> of(List<? extends E> xs, int n) {
if (n == xs.size())
return nil();
else
return cons(xs.get(n), () -> of(xs, n + 1));
}
public static <E> LazyStream<E> of(List<? extends E> xs) {
return of(xs, 0);
}
// 整数列 (low 以上 high 以下) を生成する
public static LazyStream<Integer> iota(int low, int high) {
if (low > high)
return nil();
else
return cons(low, () -> iota(low + 1, high));
}
// 2 つ遅延ストリームを func で結合する
public static <T, U, V> LazyStream<V> zipWith(BiFunction<? super T, ? super U, ? extends V> func, LazyStream<T> xs, LazyStream<U> ys) {
if (xs == NIL || ys == NIL)
return nil();
else
return cons(func.apply(xs.first(), ys.first()), () -> zipWith(func, xs.rest(), ys.rest()));
}
// 併合
public static <E extends Comparable<E>> LazyStream<E> merge(LazyStream<E> xs, LazyStream<E> ys) {
if (xs == NIL) {
return ys;
} else if (ys == NIL) {
return xs;
} else {
E x = xs.first();
E y = ys.first();
int r = x.compareTo(y);
if (r <= 0)
return cons(x, () -> merge(xs.rest(), ys));
else
return cons(y, () -> merge(xs, ys.rest()));
}
}
// 和集合
public static <E extends Comparable<E>> LazyStream<E> union(LazyStream<E> xs, LazyStream<E> ys) {
if (xs == NIL) {
return ys;
} else if (ys == NIL) {
return xs;
} else {
E x = xs.first();
E y = ys.first();
int r = x.compareTo(y);
if (r < 0)
return cons(x, () -> union(xs.rest(), ys));
else if (r > 0)
return cons(y, () -> union(xs, ys.rest()));
else
return cons(x, () -> union(xs.rest(), ys.rest()));
}
}
// 積集合
public static <E extends Comparable<E>> LazyStream<E> intersection(LazyStream<E> xs, LazyStream<E> ys) {
if (xs == NIL) {
return nil();
} else if (ys == NIL) {
return nil();
} else {
while (true) {
E x = xs.first();
E y = ys.first();
int r = x.compareTo(y);
if (r == 0) {
var xs1 = xs;
var ys1 = ys;
return cons(x, () -> intersection(xs1.rest(), ys1.rest()));
} else if (r < 0) {
xs = xs.dropWhile(x1 -> x1.compareTo(y) < 0);
} else {
ys = ys.dropWhile(y1 -> x.compareTo(y1) > 0);
}
}
}
}
//
// 基本操作
//
// 先頭要素を参照する
public E first() {
if (this == NIL)
throw new IndexOutOfBoundsException("LazyStream.first()");
return item;
}
// 次の要素を格納した遅延ストリームを返す
public LazyStream<E> rest() {
if (this == NIL)
throw new IndexOutOfBoundsException("LazyStream.rest()");
return next.force();
}
// n 番目の要素を参照する
public E get(int n) {
var xs = this;
while (n-- > 0) {
xs = xs.rest();
}
return xs.first();
}
// 要素を n 個取り出して List<E> に格納して返す
public List<E> take(int n) {
var xs = this;
var ys = new ArrayList<E>();
while (n-- > 0 && xs != NIL) {
ys.add(xs.first());
xs = xs.rest();
}
return ys;
}
// 要素を n 個取り除く
public LazyStream<E> drop(int n) {
var xs = this;
while (n-- > 0 && xs != NIL) {
xs = xs.rest();
}
return xs;
}
// 遅延ストリームの連結
public LazyStream<E> append(LazyStream<E> ys) {
if (this == NIL)
return ys;
else
return cons(first(), () -> rest().append(ys));
}
public LazyStream<E> lazyAppend(Delay<LazyStream<E>> ys) {
if (this == NIL)
return ys.force();
else
return cons(first(), () -> rest().lazyAppend(ys));
}
public LazyStream<E> interleave(LazyStream<E> ys) {
if (this == NIL)
return ys;
else
return cons(first(), () -> ys.interleave(rest()));
}
//
// 高階関数
//
// マッピング
public <U> LazyStream<U> map(Function<? super E, ? extends U> func) {
if (this == NIL)
return nil();
else
return cons(func.apply(first()), () -> rest().map(func));
}
public <U> LazyStream<U> flatMap(Function<? super E, LazyStream<U>> func) {
if (this == NIL)
return nil();
else
return func.apply(first()).lazyAppend(Delay.delay(() -> rest().flatMap(func)));
}
// フィルター
public LazyStream<E> filter(Predicate<E> pred) {
var xs = this;
while (xs != NIL) {
if (pred.test(xs.first())) {
var ys = xs;
return cons(ys.first(), () -> ys.rest().filter(pred));
}
xs = xs.rest();
}
return nil();
}
// 畳み込み
public <U> U foldLeft(BiFunction<U, ? super E, U> func, U a) {
var xs = this;
while (xs != NIL) {
a = func.apply(a, xs.first());
xs = xs.rest();
}
return a;
}
public <U> U foldRight(BiFunction<? super E, U, U> func, U a) {
if (this == NIL)
return a;
else
return func.apply(first(), rest().foldRight(func, a));
}
// 巡回
public void forEach(Consumer<? super E> func) {
var xs = this;
while (xs != NIL) {
func.accept(xs.first());
xs = xs.rest();
}
}
// 先頭から述語 pred が真を返す要素を List<E> に格納して返す
public List<E> takeWhile(Predicate<E> pred) {
var xs = this;
var ys = new ArrayList<E>();
while (xs != NIL && pred.test(xs.first())) {
ys.add(xs.first());
xs = xs.rest();
}
return ys;
}
// 先頭から述語 pred が真を返す要素を取り除く
public LazyStream<E> dropWhile(Predicate<E> pred) {
var xs = this;
while (xs != NIL && pred.test(xs.first())) {
xs = xs.rest();
}
return xs;
}
}