C#を真面目に勉強しようと思い、kekyoさんの
Final LINQ Extensions
を読んでしょっぱなから衝撃を受けた。
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番目の値を計算する。