一般的なプログラミング言語の場合、関数を呼び出す前に引数が評価され、その結果が関数に渡されます。これを「正格 (strict) な評価」といいます。これに対し、引数や変数の値が必要になるまで評価を行わない方法もあります。具体的には、引数や引数を参照するときに評価が行われます。これを「遅延評価 (delayed evaluation または lazy evaluation)」といいます。
プログラミング言語では関数型言語の Haskell が遅延評価です。また、Scheme でも delay と force を使って遅延評価を行うことができます。そして、その評価結果は保存されることに注意してください。再度変数や引数を参照すると、保存されている値が返されます。
なお、値の保存 (キャッシング) をしないでよければ、クロージャ (ラムダ式) を使って遅延評価を行うこともできます。C# はクロージャをサポートしているので、遅延評価を実装することは簡単です。今回は C# で遅延評価を行うクラス Delay<T> を作ってみましょう。
Delay<T> のコンストラクタは遅延評価を行う処理をラムダ式で受け取ります。実行はメソッド Force() で行います。このとき、評価結果がインスタンスに保存されることに注意してください。本稿では、Delay<T> のインスタンスを「遅延オブジェクト」と呼ぶことにします。再度 Force() を実行すると、保存された値が返されます。
プログラムは次のようになります。
リスト : 遅延評価
class Delay<T> {
T Result { set; get; }
bool Flag { set; get; }
Func<T> Fn { get; }
public Delay(Func<T> func) {
Result = default(T);
Flag = false;
Fn = func;
}
public T Force() {
if (!Flag) {
Result = Fn();
Flag = true;
}
return Result;
}
}
遅延評価する処理は引数無しのラムダ式で受け取ってフィールド Fn にセットします。引数なしで返り値のデータ型が T の関数は Func<T> で表すことができます。Flag は false で、Result は default(T) で初期化します。メソッド Force() は最初に Flag をチェックします。偽の場合、Fn はまだ評価されていません。Fn() を実行して、その返り値を Result にセットし、Flag を true に書き換えます。Flag が true ならば Fn は評価済みなので Result を返します。
簡単な使用例を示します。
リスト : 簡単なテスト
class Test {
static int foo(int a, int b) {
Console.Write("foo!! ");
return a + b;
}
static void Main() {
var p = new Delay<int>(() => foo(10, 20));
Console.WriteLine("{0}", p.Force());
Console.WriteLine("{0}", p.Force());
}
}
C<delay foo!! 30 30
遅延オブジェクトを変数 p にセットします。このとき、ラムダ式は評価 [*1] されていません。p.Force() を実行するとラムダ式が評価されるので、画面に foo!! が表示されて計算結果の 30 が返されます。p.Force() を再度実行すると、同じ式を再評価しないで Result に格納された値を返します。この場合 foo!! は表示されません。
遅延評価の簡単な例題として「たらいまわし関数」を取り上げます。次のリストを見てください。
リスト : たらいまわし関数
using System;
class Tarai {
static int tarai(int x, int y, int z) {
if (x <= y)
return y;
else
return tarai(tarai(x - 1, y, z),
tarai(y - 1, z, x),
tarai(z - 1, x, y));
}
static int tak(int x, int y, int z) {
if (x <= y)
return z;
else
return tak(tak(x - 1, y, z),
tak(y - 1, z, x),
tak(z - 1, x, y));
}
static void Main() {
DateTime s = DateTime.Now;
Console.WriteLine("{0}", tarai(14, 7, 0));
DateTime e = DateTime.Now;
Console.WriteLine("{0}", e - s);
s = DateTime.Now;
Console.WriteLine("{0}", tak(22, 11, 0));
e = DateTime.Now;
Console.WriteLine("{0}", e - s);
}
}
関数 tarai(), tak() は「たらいまわし関数」といって、再帰的に定義されています。これらの関数は、引数の与え方によっては実行に時間がかかるため、Lisp などのベンチマークに利用されることがあります。Common Lisp のプログラムは ぬえ 鵺 NUE の TAK Function にあります。
tarai() は通称「竹内関数」と呼ばれていて、日本の代表的な Lisper である竹内郁雄先生によって考案されたそうです。そして、tak() は tarai() のバリエーションで、John Macarthy 先生によって作成されたそうです。たらいまわし関数が Lisp のベンチマークで使われていたことは知っていましたが、このような由緒ある関数だとは思ってもいませんでした。
それでは、さっそく実行してみましょう。実行環境は Windows 7, Core i7-2670QM です。
C>tarai 14 00:00:01.7160030 11 00:00:01.9812035
このように、たらいまわし関数は引数の値が小さくても実行に時間がかかります。
たらいまわし関数は遅延評価を使って高速化することができます。tarai() のプログラムを見てください。x <= y のときに y を返しますが、このとき引数 z の値は必要ありませんね。引数 z の値は x > y のときに計算するようにすれば、無駄な計算を省略することができます。ただし、tak() は遅延評価で高速化することはできません。ご注意くださいませ。
クラス Delay<T> を使うと、たらいまわし関数は次のようになります。
リスト : Delay<T> による遅延評価
class Tarai {
static int TaraiLazy(int x, int y, Delay<int> z) {
if (x <= y) {
return y;
} else {
int zz = z.Force();
return TaraiLazy(TaraiLazy(x - 1, y, z),
TaraiLazy(y - 1, zz, new Delay<int>(() => x)),
new Delay<int>(() => TaraiLazy(zz - 1, x, new Delay<int>(() => y))));
}
}
static void Main() {
DateTime s = DateTime.Now;
Console.WriteLine("{0}", TaraiLazy(140, 70, new Delay<int>(() => 0)));
DateTime e = DateTime.Now;
Console.WriteLine("{0}", e - s);
}
}
TaraiLazy() のプログラムを見てください。遅延評価したい処理を Delay に包んで引数 z に渡します。そして、x > y のときに引数 z を評価 (z.Force()) します。すると、遅延オブジェクトのラムダ式が実行されて z の値を求めることができます。たとえば、() => 0 を Delay に渡す場合、z.Force() とすると返り値は 0 になります。() => x を渡せば、x に格納されている値が返されます。() => TaraiLazy( ... ) を渡せば、関数 TaraiLazy() が実行されてその値が返されるわけです。
それでは実行してみましょう。
C>tarailazy 140 00:00:00.0780001
tarai() の場合、遅延評価の効果はとても大きいですね。
ところで、Delay<T> を使わなくても、ラムダ式 (クロージャ) だけで遅延評価を行うことができます。次のリストを見てください。
リスト : クロージャによる遅延評価
static int TaraiLazy1(int x, int y, Func<int> z) {
if (x <= y) {
return y;
} else {
int zz = z();
return TaraiLazy1(TaraiLazy1(x - 1, y, z),
TaraiLazy1(y - 1, zz, () => x),
() => TaraiLazy1(zz - 1, x, () => y));
}
}
遅延評価したい処理をクロージャに包んで引数 z に渡します。そして、x > y のときに引数 z の関数を呼び出します。すると、クロージャ内の処理が評価されて z の値を求めることができます。たとえば、() => 0 を z に渡す場合、z() とすると返り値は 0 になります。() => x を渡せば、x に格納されている値が返されます。() => TaraiLazy1( ... ) を渡せば、TaraiLazy1() が実行されてその値が返されるわけです。ただし、クロージャでは評価結果を保存 (キャッシュ) できないことに注意してください。
「ストリーム (stream)」はデータの流れを抽象化したデータ構造です。たとえば、ファイル入出力はストリームと考えることができます。また、配列や連結リストを使ってストリームを表すこともできます。ただし、単純な配列や連結リストでは有限個のデータの流れしか表すことができません。ところが、遅延評価を用いると擬似的に無限個のデータを表すことができるようになります。これを「遅延ストリーム」とか「遅延リスト」と呼びます。今回は遅延ストリームについて簡単に説明します。
遅延ストリームの基本的な考え方は、必要になったときに新しいデータを生成することです。このときに遅延評価を用います。具体的にはデータを生成する関数を用意し、それを遅延評価してストリームに格納しておきます。そして、必要になった時点で遅延評価しておいた関数を呼び出して値を求めればよいわけです。
今回は遅延ストリームを表すクラス LazyS<T> を作成することにします。プログラムは次のようになります。
リスト : 遅延ストリーム
class LazyS<T> {
T Car;
Delay<LazyS<T>> Cdr;
public LazyS(T item, Func<LazyS<T>> func) {
Car = item;
Cdr = new Delay(func);
}
// 終端
public static readonly LazyS<T> nil = new LazyS<T>(default(T), () => nil);
public bool IsEmpty() { return this == nil; }
public T StreamCar() { return Car; }
public LazyS<T> StreamCdr() { return Cdr.Force(); }
}
フィールド Car に現時点での先頭データを格納し、フィールド Cdr に遅延ストリームを生成する Delay<LazyS<T>> を格納します。これを Force() することで、次の要素を格納した遅延ストリームを生成します。nil はストリームの終端を表します。無限ストリームだけを扱うのであれば nil は必要ありません。
メソッド StreamCar() は遅延ストリームから要素を取り出して返します。メソッド StreamCdr() は遅延ストリームの Cdr を Force() して、次の要素を格納した遅延ストリームを生成して返します。ようするに、これらのメソッドは Lisp / Scheme のリスト操作関数 cons, car, cdr に対応しているわけです。
それでは、遅延ストリームを生成するメソッドを作りましょう。たとえば、start から count 個の整数列を生成するストリームは次のようにプログラムすることができます。
リスト : 整数列を生成するストリーム
public static LazyS<int> Range(int start, int count) {
if (count == 0)
return LazyS<int>.nil;
else
return new LazyS<int>(start, () => Range(start + 1, count - 1));
}
メソッド Range() は遅延ストリームを生成して返します。LazyS<int> のコンストラクタの第 1 要素が現時点でのデータになります。第 2 引数にはラムダ式を渡して、その中で Range() を呼び出します。StreamCdr() を実行すると、遅延オブジェクトに格納されたラムダ式が評価され、その本体である Range() が実行されて次のデータを格納した遅延ストリームが返されます。その遅延ストリームに対してさらに StreamCdr() を実行すると、その次のデータを得ることができます。
簡単な例を示しましょう。
リスト : 整数列の生成
class Test {
static void Main() {
var s1 = LazyS<int>.Range(1, 10);
while (!s1.IsEmpty()) {
Console.WriteLine("{0}", s1.StreamCar());
s1 = s1.StreamCdr();
}
}
}
C>delay 1 2 3 4 5 6 7 8 9 10
このように、StreamCdr() を実行することで、次々とデータを生成することができます。
もう一つ、簡単な例を示しましょう。フィボナッチ数列を生成する遅延ストリームを作ります。次のリストを見てください。
リスト : フィボナッチ数列を生成する遅延ストリーム
public static LazyS<long> Fibonacci(long a = 0, long b = 1) {
return new LazyS<long>(a, () => Fibonacci(b, a + b));
}
メソッド Fibonacci() の引数 a がフィボナッチ数列の最初の項で、b が次の項です。したがって、ラムダ式に Fibonacci(b, a + b) を格納しておけば、StreamCdr() を実行することでフィボナッチ数列を生成することができます。なお、このメソッドは無限ストリームを生成しますが、C# の整数 (long) には上限値があるので、際限なくフィボナッチ数列を生成できるわけではありません。ご注意ください。
次は遅延ストリームを操作するメソッドを作りましょう。最初は n 番目の要素を求めるメソッド StreamRef() です。
リスト : n 番目の要素を求める
public T StreamRef(int n) {
var xs = this;
while (n-- > 0 && xs != nil) {
xs = xs.StreamCdr();
}
return xs.StreamCar();
}
StreamRef() は StreamCdr() を n 回繰り返して n 番目の要素を求めるだけです。
ストリームから n 個の要素を取り出して List<T> に格納して返すメソッド StreamTake() と先頭から n 個の要素を取り除くメソッド StreamDrop() も同様にプログラムすることができます。
リスト : n 個の要素を取り出す
public List<T> StreamTake(int n) {
var ys = new List<T>();
var xs = this;
while (n-- > 0 && xs != nil) {
ys.Add(xs.StreamCar());
xs = xs.StreamCdr();
}
return ys;
}
public LazyS<T> StreamDrop(int n) {
var xs = this;
while (n-- > 0 && xs != nil) {
xs = xs.StreamCdr();
}
return xs;
}
StreamTake() は StreamCar() と StreamCdr() を n 回繰り返して、要素を List<T> に格納して返します。StreamDrop() は StreamCdr() を n 回繰り返すだけです。
簡単な実行例を示しましょう。
リスト : フィボナッチ数列のテスト
class Test {
static void Main() {
var s2 = LazyS<long>.Fibonacci();
for (int i = 0; i < 20; i++) {
Console.Write("{0} ", s2.StreamRef(i));
}
foreach(long x in s2.StreamDrop(20).StreamTake(10)) {
Console.WriteLine("{0}", x);
}
}
}
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
変数 s2 にフィボナッチ数列を生成するストリームをセットします。StreamRef() で順番に要素を 20 個取り出すと、その値はフィボナッチ数列になっていますね。同様に、StreamDrop() で 20 個の要素を取り除き、StreamTake() で 10 個の要素を取り出します。すると、その要素は 20 番目以降のフィボナッチ数列になります。
ところで、遅延ストリームは高階関数も定義することができます。次のリストを見てください。
リスト : 高階関数
// マッピング
public LazyS<U> StreamMap<U>(Func<T, U> func) {
if (this == nil)
return LazyS<U>.nil;
else
return new LazyS<U>(func(StreamCar()), () => StreamCdr().StreamMap(func));
}
// フィルター
public LazyS<T> StreamFilter(Func<T, bool> pred) {
if (this == nil)
return nil;
else if (pred(StreamCar()))
return new LazyS<T>(StreamCar(), () => StreamCdr().StreamFilter(pred));
else
return StreamCdr().StreamFilter(pred);
}
// 畳み込み
public U StreamFoldLeft<U>(Func<U, T, U> func, U a) {
var xs = this;
while (xs != nil) {
a = func(a, xs.StreamCar());
xs = xs.StreamCdr();
}
return a;
}
public U StreamFoldRight<U>(Func<T, U, U> func, U a) {
if (this == nil)
return a;
else
return func(StreamCar(), StreamCdr().StreamFoldRight(func, a));
}
StreamMap() と StreamFilter() は関数と遅延ストリームを受け取り、新しい遅延ストリームを生成して返します。StreamMap() は引数のストリームの要素に関数 func を適用した結果を新しいストリームに格納して返します。StreamFilter() は述語 pred が真を返す要素だけを新しいストリームに格納して返します。
StreamFoldLeft() と StreamFoldRight() は遅延ストリームに対して畳み込み処理を行います。無限ストリームの場合は処理が終了しないので注意してください。
簡単な実行例を示しましょう。
リスト : 高階関数のテスト
class Test {
static void Main() {
var s3 = LazyS<int>.Range(1, 100);
var s4 = s3.StreamMap(n => n * n);
foreach(int x in s4.StreamTake(10)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
var s5 = s3.StreamFilter(n => n % 2 == 0);
foreach(int x in s5.StreamTake(10)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
Console.WriteLine("{0}", s3.StreamFoldLeft((sum, n) => sum + n, 0));
Console.WriteLine("{0}", s3.StreamFoldRight((n, sum) => sum + n, 0));
}
}
C>delay 1 4 9 16 25 36 49 64 81 100 2 4 6 8 10 12 14 16 18 20 5050 5050
変数 s3 に 1 から始まる整数列を生成するストリームをセットします。次に、s3 の要素を 2 乗するストリームを StreamMap() で生成して変数 s4 にセットします。StreamTake() で s4 から要素を 10 個取り出すと、s3 の要素を 2 乗した値になります。
s3 から偶数列のストリームを得るには、引数が偶数のときに真を返す述語を StreamFilter() に渡します。その返り値を変数 s5 にセットして、StreamTake() で 10 個の要素を取り出すと、リストの要素は 2 から 20 までの値になります。
s3 は有限個の遅延ストリームなので畳み込みを行うことができます。StreamFoldLeft() と StreamFoldRight() で要素の合計値を求めると 5050 になります。
次はストリームを使って素数を求めるプログラムを作ってみましょう。考え方は簡単です。最初に、2 から始まる整数列を生成するストリームを用意します。2 は素数なので、素数ストリームの要素になります。次に、この整数列から 2 で割り切れる整数を取り除き除きます。これは StreamFilter() を使うと簡単です。
2 で割り切れる整数が取り除かれたので、次の要素は 3 になります。今度は 3 で割り切れる整数を取り除けばいいのです。これも StreamFilter() を使えば簡単です。このとき、入力用のストリームは 2 で割り切れる整数が取り除かれています。したがって、このストリームに対して 3 で割り切れる整数を取り除くように StreamFilter() を設定すればいいわけです。
このように、素数を見つけたらそれで割り切れる整数を取り除いていくアルゴリズムを「エラトステネスの篩」といいます。ようするに、2 から始まる整数ストリームに対して、見つけた素数 2, 3, 5, 7, 11, ... を順番に StreamFiter() で設定して素数でない整数をふるい落としていくわけです。
プログラムは次のようになります。
リスト : 素数の生成
class Test {
// 素数
static LazyS<int> Sieve(LazyS<int> s) {
int p = s.StreamCar();
return new LazyS<int>(p, () => Sieve(s.StreamCdr().StreamFilter(n => n % p != 0)));
}
static void Main() {
var s6 = Sieve(LazyS<int>.Range(2, 10000));
foreach(int x in s6.StreamTake(100)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
}
}
Sieve() には 2 から始まる整数列を生成するストリームを渡します。遅延オブジェクトを評価すると、StreamFilter() により整数列から 2 で割り切れる整数を取り除いたストリームが返されます。次の要素 3 を取り出すとき、このストリームに対して 3 で割り切れる整数を取り除くことになるので、2 と 3 で割り切れる整数が取り除かれることになります。次の要素は 5 になりますが、そのストリームからさらに 5 で割り切れる整数が StreamFilter() で取り除かれることになります。
このように StreamFilter() が設定されていくことで、素数でない整数をふるい落としていくことができるわけです。それでは実行してみましょう。
C>delay 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 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541
正常に動作していますね。
次は、2 つの遅延ストリームを受け取って 1 つの遅延ストリームを返すメソッドを考えてみましょう。一番簡単な操作は 2 つのストリームを連結することです。次のリストを見てください。
リスト : 遅延ストリームの連結
public LazyS<T> StreamAppend(LazyS<T> xs) {
if (this == nil)
return xs;
else
return new LazyS<T>(StreamCar(), () => StreamCdr().StreamAppend(xs));
}
関数 StreamAppend() は自分 (this) と引数のストリーム xs を連結したストリームを返します。処理は簡単で、自分の要素を順番に取り出していき、空になったら xs を返すだけです。
次は 2 つの遅延ストリームの要素を交互に出力する遅延ストリームを作ります。次のリストを見てください。
リスト : ストリームの要素を交互に出力 public LazySInterleave(LazyS xs) { if (this == nil) return xs; else return new LazyS (StreamCar(), () => xs.Interleave(StreamCdr())); }
メソッド Interleave() は自分 (this) のほかに引数 xs に遅延ストリームを受け取ります。そして、自分の要素を新しいストリームに格納したら、次は xs の要素を新しいストリームに格納します。これは遅延オブジェクトで Interleave を呼び出すとき、xs に対して Interleave() を呼び出し、引数に StreamCdr() の結果を渡すだけです。これで要素を交互に出力することができます。
簡単な実行例を示しましょう。
リスト : 遅延ストリームの連結
class Test {
static void Main() {
var s7 = LazyS<int>.Range(1, 4);
var s8 = LazyS<int>.Range(5, 8);
var s9 = s7.StreamAppend(s8);
foreach(int x in s9.StreamTake(8)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
foreach(int x in s7.Interleave(s8).StreamTake(8)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
}
}
C>delay 1 2 3 4 5 6 7 8 1 5 2 6 3 7 4 8
StreamAppend() の場合、無限ストリームを連結することはできませんが、Interleave() ならば無限ストリームにも対応することができます。簡単な例を示しましょう。
リスト : 1 と 2 の無限数列 public static readonly LazyS<int> ones = new LazyS<int>(1, () => ones); public static readonly LazyS<int> twos = new LazyS<int>(2, () => twos);
ones は 1 を無限に出力するストリームで、twos は 2 を無限に出力するストリームです。どちらもクラス LazyS<T> の中で定義します。StreamAppend() で ones と twos を連結しても無限に 1 を出力するだけですが、Interleave() で ones と twos を連結すれば、1 と 2 を交互に出力することができます。これで無限ストリームの要素を混ぜ合わせることができます。
簡単な実行例を示します。
リスト : 無限ストリームの連結
class Test {
static void Main() {
foreach(int x in LazyS<int>.ones.StreamTake(8)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
foreach(int x in LazyS<int>.twos.StreamTake(8)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
foreach(int x in LazyS<int>.ones.Interleave(LazyS<int>.twos).StreamTake(10)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
}
}
C>delay 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1 2 1 2 1 2 1 2 1 2
正常に動作していますね。
ところで、今回の遅延ストリームは Delay<T> を使っているので、評価値のキャッシングが行われますが、それをしなくてもよければ、C# のイテレータや LINQ を使って遅延ストリームと同様な動作を実現することができます。
イテレータ (yield return) で値を返す場合、返り値の型は IEnumerable, IEnumerable<T>, IEnumerator, IEnumerator<T> のいずれかであることが必要ですが、LINQ といっしょに使う場合は IEnumerable<T> にすると上手くいきます。
簡単な実行例を示します。
//
// lazy.cs : イテレータと LINQ による遅延ストリーム
//
// Copyright (C) 2016 Makoto Hiroi
//
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
class Test {
// Enumerable.Range() があるので不要
static IEnumerable<int> Range(int start, int count) {
while (count-- > 0) {
yield return start++;
}
}
static IEnumerable<long> Fibonacci() {
long a = 0, b = 1;
while (true) {
yield return a;
long c = a;
a = b;
b += c;
}
}
static IEnumerable<int> Sieve(IEnumerable<int> s) {
while (true) {
int p = s.ElementAt(0);
yield return p;
s = s.Skip(1).Where(n => n % p != 0);
}
}
static void Main() {
var s1 = Range(1, 10000);
var s2 = s1.Select(n => n * n);
foreach(int x in s2.Take(10)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
var s3 = s1.Where(n => n % 2 == 0);
foreach(int x in s3.Take(10)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
var s4 = Fibonacci();
foreach(long x in s4.Take(20)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
var s5 = s4.Skip(20);
foreach(long x in s5.Take(20)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
foreach(int x in Sieve(Range(2, 10000)).Take(100)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
}
}
C<lazy 1 4 9 16 25 36 49 64 81 100 2 4 6 8 10 12 14 16 18 20 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 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 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541
//
// delay.cs : 遅延評価
//
// Copyright (C) 2016 Makoto Hiroi
//
using System;
using System.Collections;
using System.Collections.Generic;
// 遅延評価
class Delay<T> {
T Result { set; get; }
bool Flag { set; get; }
Func<T> Fn { get; }
public Delay(Func<T> func) {
Result = default(T);
Flag = false;
Fn = func;
}
public T Force() {
if (!Flag) {
Result = Fn();
Flag = true;
}
return Result;
}
}
// 遅延ストリーム
class LazyS<T> {
T Car;
Delay<LazyS<T>> Cdr;
public LazyS(T item, Func<LazyS<T>> func) {
Car = item;
Cdr = new Delay<LazyS<T>>(func);
}
// 終端
public static readonly LazyS<T> nil = new LazyS<T>(default(T), () => nil);
public bool IsEmpty() { return this == nil; }
public T StreamCar() { return Car; }
public LazyS<T> StreamCdr() { return Cdr.Force(); }
// 整数列の生成
public static LazyS<int> Range(int start, int count) {
if (count == 0)
return LazyS<int>.nil;
else
return new LazyS<int>(start, () => Range(start + 1, count - 1));
}
// フィボナッチ数列の生成
public static LazyS<long> Fibonacci(long a = 0, long b = 1) {
return new LazyS<long>(a, () => Fibonacci(b, a + b));
}
// 1 と 2 の無限数列
public static readonly LazyS<int> ones = new LazyS<int>(1, () => ones);
public static readonly LazyS<int> twos = new LazyS<int>(2, () => twos);
// 参照
public T StreamRef(int n) {
var xs = this;
while (n-- > 0 && xs != nil) {
xs = xs.StreamCdr();
}
return xs.StreamCar();
}
// 要素を取り出す
public List<T> StreamTake(int n) {
var ys = new List<T>();
var xs = this;
while (n-- > 0 && xs != nil) {
ys.Add(xs.StreamCar());
xs = xs.StreamCdr();
}
return ys;
}
// 要素を取り除く
public LazyS<T> StreamDrop(int n) {
var xs = this;
while (n-- > 0 && xs != nil) {
xs = xs.StreamCdr();
}
return xs;
}
// 高階関数
// マッピング
public LazyS<U> StreamMap<U>(Func<T, U> func) {
if (this == nil)
return LazyS<U>.nil;
else
return new LazyS<U>(func(StreamCar()), () => StreamCdr().StreamMap(func));
}
// フィルター
public LazyS<T> StreamFilter(Func<T, bool> pred) {
if (this == nil)
return nil;
else if (pred(StreamCar()))
return new LazyS<T>(StreamCar(), () => StreamCdr().StreamFilter(pred));
else
return StreamCdr().StreamFilter(pred);
}
// 畳み込み
public U StreamFoldLeft<U>(Func<U, T, U> func, U a) {
var xs = this;
while (xs != nil) {
a = func(a, xs.StreamCar());
xs = xs.StreamCdr();
}
return a;
}
public U StreamFoldRight<U>(Func<T, U, U> func, U a) {
if (this == nil)
return a;
else
return func(StreamCar(), StreamCdr().StreamFoldRight(func, a));
}
// 連結
public LazyS<T> StreamAppend(LazyS<T> xs) {
if (this == nil)
return xs;
else
return new LazyS<T>(StreamCar(), () => StreamCdr().StreamAppend(xs));
}
public LazyS<T> Interleave(LazyS<T> xs) {
if (this == nil)
return xs;
else
return new LazyS<T>(StreamCar(), () => xs.Interleave(StreamCdr()));
}
}
class Test {
// 素数
static LazyS<int> Sieve(LazyS<int> s) {
int p = s.StreamCar();
return new LazyS<int>(p, () => Sieve(s.StreamCdr().StreamFilter(n => n % p != 0)));
}
static void Main() {
var s1 = LazyS<int>.Range(1, 10);
while (!s1.IsEmpty()) {
Console.WriteLine("{0}", s1.StreamCar());
s1 = s1.StreamCdr();
}
var s2 = LazyS<long>.Fibonacci();
for (int i = 0; i < 20; i++) {
Console.Write("{0} ", s2.StreamRef(i));
}
foreach(long x in s2.StreamDrop(20).StreamTake(10)) {
Console.WriteLine("{0}", x);
}
var s3 = LazyS<int>.Range(1, 100);
var s4 = s3.StreamMap(n => n * n);
foreach(int x in s4.StreamTake(10)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
var s5 = s3.StreamFilter(n => n % 2 == 0);
foreach(int x in s5.StreamTake(10)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
Console.WriteLine("{0}", s3.StreamFoldLeft((sum, n) => sum + n, 0));
Console.WriteLine("{0}", s3.StreamFoldRight((n, sum) => sum + n, 0));
var s6 = Sieve(LazyS<int>.Range(2, 10000));
foreach(int x in s6.StreamTake(100)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
var s7 = LazyS<int>.Range(1, 4);
var s8 = LazyS<int>.Range(5, 8);
var s9 = s7.StreamAppend(s8);
foreach(int x in s9.StreamTake(8)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
foreach(int x in s7.Interleave(s8).StreamTake(8)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
foreach(int x in LazyS<int>.ones.StreamTake(8)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
foreach(int x in LazyS<int>.twos.StreamTake(8)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
foreach(int x in LazyS<int>.ones.Interleave(LazyS<int>.twos).StreamTake(10)) {
Console.Write("{0} ", x);
}
Console.WriteLine("");
}
}