C#を真面目に勉強しようと思い、kekyoさんの
を読んでしょっぱなから衝撃を受けた。 C#ってこんなに簡単に無限列が書けるんだ！
イテレータと無限列
たとえば0の無限列のイテレータは以下の通り。
public static IEnumerable<int> Infinity() { while(true) yield return 0; }
以下はInfinityを用いて0を100回出力するコード。
public static void Main (string[] args) { Console.WriteLine(string.Join("\n", Infinity().Take(100))); }
Fibonacci数列なら以下のように書ける。
public static IEnumerable<ulong> Fib(){ yield return 0; yield return 1; foreach (var k in Fib().Skip(1).Zip(Fib(), (m, n) => m + n)) { yield return k; } } public static void Main (string[] args) { foreach (var n in Fib().Take(40)) { Console.WriteLine(n); } }
書ける。が、上記のコードは再帰を使っており遅い。そこで、メモ化して線形時間で計算できるようにする。
public static IEnumerable<ulong> MemoFib(){ ulong predpred = 0; ulong pred = 1; yield return predpred; yield return pred; while (true) { ulong current = predpred + pred; predpred = pred; pred = current; yield return current; } }
無事に書けた。が、メモ化により状態管理のコードが混ざったため、先ほどのfib実装が宣言的に書けているのに比べると手続き的だ。 また、メモ化自体は様々な無限列で必要になりうる。そこで、メモ化の仕組みと再帰的な数列生成の部分を切り分けたい。
メモ化
というわけで下のように切り分けた。
public static IEnumerable<T> memoize<T>(Func<Func<int, T>, int, T> generator){ Dictionary<int, T> memo = new Dictionary<int, T>(); T accessor (int n){ if (!memo.ContainsKey(n)) memo[n] = generator(accessor, n); return memo[n]; }; int i = 0; while(true) yield return accessor(i++); } public static ulong FibFactory (Func<int, ulong>accessor,int i){ switch (i) { case 0: case 1: return (ulong)i; default: return accessor(i - 2) + accessor(i - 1); }; } public static void Main (string[] args) { foreach (var n in memoize<ulong> (FibFactory).Take(80)) { Console.WriteLine (n); } }
memoize内部のaccessor関数はメモテーブルの読み出しをラップし、すでに値が計算されていればテーブルの値を使い、そうでなければgeneratorを用い値を計算する。 generatorはaccessorとindexを受け取り、数列のindex番目の値を計算する。
