C# 3.0 と List

.NET

さて，上の話 (id:NyaRuRu:20070722:p1) のカウンターウェイトとして書いておきたいのですが，実際問題として C# で再帰的なラムダ式を必要とする場面はそれほど多くはないと思っています．たとえば先ほどの階乗関数は，N <= 0 の場合を除いて以下のように書くことができるでしょう(先ほどの例でも N < 0 は無視してきましたが)．

Func<int, int> fact =
    N => Enumerable.Range(1, N).Aggregate((ret, n) => n * ret);

1 * 2 * 3 * ...... * N を集約によって求めています．このように定義した fact は，N が増えてもスタックの消費量は一定です．
Aggregate は F# の fold と同等と見ることができそうです．N = 0 も含めるとすればこんな感じでしょう．

Func<int, int> fact2 =
    N => Enumerable.Concat
         (
            Enumerable.Repeat(1, 1), // fact(0)
            Enumerable.Range(1, N)
         ).Aggregate((ret, n) => n * ret);

個人的には『Concepts behind the C# 3.0 language』で色々な関数型言語と対比されているコードも好みです．たとえば， Haskell と比較されているフィボナッチ数列を見てみましょう．

-- Haskell
fibs = 0 : 1 : [a + b | (a, b) <- zip fibs (tail fibs)]

// C# 3
var fibs = new InfiniteList<int>((t) => 
  t.ZipWith(t.Tail()).Select((v) => v.First + v.Second),
  0, 1);

Semantics of both examples are same. The list of Fibonacci numbers is declared recursively using already known elements in the list. The generator section in C# - t.ZipWith(t.Tail()) is equivalent to zip fibs (tail fibs) written in Haskell. In the C# version, it is not possible to reference fibs variable while it is being initialized, so the t is instance of the list passed to the generator to allow recursive declarations. The projection secion in C# - Select((v) => v.First + v.Second) is equivalent to a + b | (a, b) from Haskell, the difference here is that C# doesn’t directly support tuples, so tuple is represented as structure with members First and Second. The filtering section is not used in this example and finally, the last two parameters (0, 1) define initial values in the list which is equal to declaration of first two values in Haskell (0 : 1 : …).

C# 3.0 のコードで使われている InfiniteList も ZipWith も，LINQ に標準で存在するわけではなく，同等物を定義できるというコンセプトコードですが，なかなかにいい味を出しています．
上で私が定義した fact は，引数 n に対しての値は返すものの，その計算途中の値は捨ててしまいます．一方でこの fibs は無限リストになっていて (といってもこのままではすぐにオーバーフローしてしまいますが)，順番に数列の値を返しながら計算を続けていくことができます．必要になったときに Take メソッドで必要なだけ取り出せば，必要なだけ計算が行われるというわけです．
さて，Aggregate が fold に対応したことを思い出せば，unfold の C# 版があると，(無限) リストを作り出すのに何かと便利そうです．以下は『Foundations of F#』よりの抜粋です．

//F#
#light
let fibs =
    (1, 1) |> Seq.unfold
        (fun (n0, n1)  ->
            Some(n0, (n1, n0 + n1)))

let first20 = Seq.take 20 fibs

print_any first20

私も Nullable を使って作ってみたのですが，匿名型をサポートしようとするとかなり汚いコードになってしまい，少し考慮中といったところです．興味がある方はぜひ挑戦してみてください．良いのができたら教えていただけると幸いです．