読者です 読者をやめる 読者になる 読者になる

熟練した C# 使いは再帰を書かない?

.NET

Y Combinator は私も『C# 3.0 と不動点演算子 - NyaRuRuの日記』で取り上げましたが,実際使っているかというと全然使ってないです.実際は Enumerable.Aggregate や,以前取り上げた unfoldAchiral での Cascade ほにゃらら等々の再帰的リスト操作関数で書いてます.
目指すは yhara くんのこの境地ですかねぇ.

熟練したScheme使いは再帰を書かない

いや書かないは嘘だけど、リストを扱う関数が充実してるので自分で再帰してどうこう…っていうのはあまりしなくていいことが最近分かってきた。例えばfoldとか。

再帰構造を便利関数に変換して書けば,C# でも工夫次第でスタック消費を減らすことができますし,yield が匿名メソッドで使えないという制限も気にしなくて済みます.関数名を見ればどんな再帰構造なのかが分かるのでその辺も便利と.

Achiral 版 Fib

そういや Achiral ではまだ unfold 作ってなかったなぁ.CascadeBreadthFirst で代用できると気付いてまあいいやとほったらかしだったかも.

using System;
using System.Collections.Generic;
using System.Linq;
using Achiral;
using Achiral.Extension;

static class Program
{
    // http://d.hatena.ne.jp/yuji1982/20080124/1201177935
    static public IEnumerable<int> Fib(int count)
    {
        foreach (int ii in Enumerable.Range(0, count))
            yield return Make.Fix<int>(ff => i => ((i < 2) ? 1 : ff(i - 1) + ff(i - 2)))(ii);
    }

    static void Main(string[] args)
    {
        var fibseq = Make.Func((Tuple<int, int> p) => Make.Sequence(Make.Tuple(p.Item2, p.Item1 + p.Item2)))
                         .CascadeBreadthFirst(Make.Tuple(1, 1))
                         .Select(pair => pair.Item1);
        var fib2 = Make.Func((int n) => fibseq.Take(n));

        Console.WriteLine(Fib(10).SequenceEqual(fib2(10)));
    }
}

もし unfold を作るなら,Func<T, T> への拡張メソッドで作るというのもひとつの手ですな.

簡易版 unfold

public static class FuncUtil
{
    public static IEnumerable<T> Unfold<T>(this Func<T, T> func, T seed)
    {
        while (true)
        {
            yield return seed;
            seed = func(seed);
        }
    }
}

こんな感じでひとつ作っておくと便利.