Haskellっぽくフィボナッチ数列を書きつつIEnumerableの評価タイミングを確認

C# Advent Calendar 2014のハードルが高くならないうちにお題を一つと2日目に手を挙げさせていただいた次第。

さて、関数型言語らしい数列定義というのを教えてもらったのでじゃあC#で書いてみよう！とやってみたところ…という話。

ではまず解説抜きで、Haskellらしいとされるフィボナッチ数列の書き方がこれです。

fib = 0:1:zipWith (+) fib (tail fib)

この関数定義の読み方です。

• :は【先頭の値】と【残りのリスト】を連結してリストを定義する演算子です。
  zipWith (+) fib (tail fib)と定義されたリストの頭に1を、さらに0を連結したものを表しています。
• tailとはリストから先頭を取り除いた残りのリストを取り出す関数です。関数型言語のリストとLINQのIEnumerableの違いを無視するなら.Skip(1)だと言えます。
• C#なら(x, y) => x + yとラムダ式で書くところを(+)と書けてしまうのはうらやましいですね。
• zipWithはLINQで言うところの.Zip、2本のリストから一個ずつ要素を取り出してそれらの演算結果をリストとして返す関数です。zipWith (+) fib (tail fib)はIEnumerableならばfib.Zip(fib.Skip(1), (x, y) => x + y) と書いてあるようなもの。

全体として、先頭が0, 1で始まるのはいいとして、残りのリストを定義するのに自分自身を利用しているところが非常に“らしい”わけです。

さて意味がわかったところで、同じものをLINQで書き下ろしてみようと取りかかります。

IEnumerable<int> fib = new int[] { 0, 1 }.Concat(fib.Zip(fib.Skip(1), (x, y) => x + y));

逐語訳してみたつもりですが、これはアウトです。これがローカル変数宣言だとしたら未定義の変数を使用しているとコンパイルエラーになりますし、これがフィールド宣言だとしたら定義の時点ではまだfibがnullなせいで実行時にNullRefernceExceptionが飛びます。

なるほど、確かに“関数型言語らしい”関数定義ではないですか。

さてここで思い出します。これ、無名関数で再帰が書けない悩みじゃないか。こんな感じの0引数Recurse関数を用意してあげれば再帰的に自己を参照して…

IEnumerable<int> fib = Recurse<IEnumerable<int>>(self =>
  new int[] { 0, 1 }.Concat(self.Zip(self.Skip(1), (x, y) => x + y)));

とやると、今度は実行時にスタックオーバーフローです。はい、再帰関数を書くには重要なルールがあるのを忘れていました。必ず到達できる脱出条件があることです。この定義、到達うんぬん以前に脱出条件がありません。

ということは、これも同じでダメですね。

IEnumerable<int> Fib()
{
  return new int[] { 0, 1 }.Concat(Fib().Zip(Fib().Skip(1), (x, y) => x + y));
}

気持ちよくStackOverflowExceptionをかっ飛ばします。

解決１：fibを遅延評価していただきたい

最初のラムダ式定義、何が悪かったかというと定義式中の"fib"がその場で評価されていたからです。だからまだ評価できませんよってコンパイルエラーもらったり問答無用でnullに評価されてこけたりしていました。

じゃあこんなものを用意してみましょう。

/// <remark>IEnumerableを返すデリゲートfactoryを取って、IEnumerableを返す。
/// 返されたIEnumerableを列挙するときに初めてfactoryは評価される</remark>
static IEnumerable<T> Delayed<T>(Func<IEnumerable<T>> factory)
{
  // 実装略。
}

実装略なのは普通に書こうとするとクラス2個実装しないといけないから。Javaの匿名クラスがたまにうらやましくなりますね…　クラス作らなくてもいい書き方もあるのですがそれは後で。
とにかく、これを使ってDelayed(() => fib)と書けば、そのオブジェクトがforeachなりToArrayなりされるときに初めてfibは評価されます。

そうしますと。

IEnumerable<int> fib = new int[] { 0, 1 }.Concat(Delayed(() => fib).Zip(Delayed(() => fib).Skip(1), (x, y) => x + y));

これはOK。通るし走ります。

解決２：0:1:の逐語訳ってむしろyield returnじゃないの？

何かちゃぶ台返しきました。確かにnew int[] { 0, 1 }.Concat(...は、リストの先頭に1をくっつけてその前に0をくっつけてという関数定義の逐語訳とは言いがたい。

  yield return 0;
  yield return 1;
  ...

の方がまだ近いのではと思えてきます。それではこれで試しに書いてみましょう。

IEnumerable<int> Fib()
{
  yield return 0;
  yield return 1;
  foreach (int n in Fib().Zip(Fib().Skip(1), (x, y) => x + y)) yield return n;
}

えっこれもしかしてうまくいくんじゃない？　→その通りで、通るし走ります。
さてこれがなんで走るかです。再帰呼び出しをしていてかつ脱出条件の記述がどこにもありません。なぜ無限再帰に陥らない？

yield returnを使ったメソッド定義の特殊さのせいですね。マイクロスレッドのようなオブジェクトにごっそり書き換えられる糖衣構文で、yield returnのたびに制御を返す動きになるため、スタックの動きをなぞっていけばyield return 0;やyield return 1;が脱出条件として働いています。コードづらから見えにくいですが。

ちなみにIEnumerableオブジェクトは生成される一方で破棄されないのでスタックオーバーフローは起こさずともそのうちメモリ食いつぶして死にますごめんなさい。

もちろん解決１のやつも同じ理由で列挙続けてるとメモリ食いつぶして死にます。ここらへんが関数型のリスト構造と、IEnumeratorを毎回作るしかないIEnumerableとの違いですか。

yield returnがそういう風ならDelayed()も書きやすいんじゃない？

上のyield return使ったメソッド、必要になっていない時点（yield return 0;で返す段階）ではまだ自己を再帰呼び出ししないから無限再帰に陥らずに済んでいた、ということはあれ、必要なときまで評価を先送りするやつやってくれているってことではありませんか。

さっき面倒だからと実装を省略してしまったDelayed()メソッド、もしかしてシンプルに書ける…？

static IEnumerable<T> Delayed<T>(Func<IEnumerable<T>> factory)
{
  foreach (T element in factory()) yield return element;
}

超簡単だった。

まとまるんですかねこれ

yield returnおもしろいし便利なので積極的に使っていきたいし手続き型各言語の皆様これ絶対あった方がいいので採用してください。