読者です 読者をやめる 読者になる 読者になる
ようこそ。睡眠不足なプログラマのチラ裏です。

ラムダとY Combinatorと私。Y Combinatorは恐ろしい子。

プログラミング アルゴリズム LINQ C#3.0

再帰的な関数を作る場合に、その関数に名前をつけずに定義するにはどうすればよいの?*1
というのがY Combinatorの中心的話題のようだ。
つまり、不動点演算子を用いると、ラムダ式で再帰表現できるというお話。

f(x) = x なる x が不動点となるのであった。f(x) の具体的な式がわかれば不動点がわかるのは前述したとおりだが、わからない場合でもどうにかならないか、と考えてみる。そこで、この問題を抽象的に捉え、f(x) = x の条件を満たす x を算出する関数 g(f) を仮定してみるのだ。そうすると、f(x) = x なる x は g(f) であるので、x に g(f) を代入してもこの条件は成立するのであり、よって、f(g(f)) = g(f) が導かれる。

なんと、この f(g(f)) = g(f) が不動点演算子と呼ばれる、再帰を表す関数なのである。


元ネタフドーテンが倒せない - いげ太のブログ

Y Combinator(不動点演算子の一種)*2について、ググって勉強していました。
いろいろな記事を拝見しましたが、いげ太さんのブログの解説が自分には一番しっくりきました。
とても丁寧に解説されていて、わかりやすいです。Y Combinatorってなんぞや?って方はぜひご一読を。
(タイトルも洒落がきいてて素敵ですw)


C#ラムダ式でY Combinatorを書いてみる

        /// <summary>
        /// Y Combinatorみたいなやつ
        /// </summary>
        static Func<T,Fix<T,Func<Func<T,>> F)
        {
            return t => F(Fix(F))(t);
        }

元ネタ: Y Combinatorが凄すぎる! - yuji1982の日記

確かにこのFix関数はY Combinatorと同じ動きと役割を果たしますが、
自身で自身の関数を呼んでいるので、厳密にはY Combinatorではないようです。


そこで、delegateとラムダ式を使って、C#でY CombinatorなFix関数を書いてみる。

        delegate Func<T, TResult> Recursive<T, TResult>(Recursive<T, TResult> f);
        static public Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> lambda)
        {
            Func<Func<Func<T, TResult>, Func<T, TResult>>, Func<T, TResult>>
            y = f => ((Recursive<T, TResult>)(g => x => f(g(g))(x)))
                     ((Recursive<T, TResult>)(g => x => f(g(g))(x)));
            return y(lambda);
        }

え〜と・・・。なんかえらいことになってます(笑)



Y Combinatorで「エラトステネスの篩」

では、作成したFix関数で実際に、不動点演算子ラムダ式による再帰表現をしてみましょう。
題材は、Haskellで書いた「エラトステネスの篩」にしてみます。

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1
{
    static class Program
    {
        static void Main()
        {
            //エラトステネスの篩
            var sieveOfEratosthenes = Fix<IEnumerable<int>, IEnumerable<int>>(
                fact => nums =>
                {
                    return from num in nums
                           where IsPrimeNumber(num)
                           select num;
                });
            sieveOfEratosthenes(Enumerable.Range(2, 99)).ForEach(s => Console.WriteLine(s));
            Console.ReadLine();
        }
        private static bool IsPrimeNumber(this int value)
        {
            if (value < 2) return false;
            for (var i = 2; i <= value / 2; ++i)
            {
                if (value % i == 0) return false;
            }
            return true;
        }

        delegate Func<T, TResult> Recursive<T, TResult>(Recursive<T, TResult> f);
        static public Func<T, TResult> Fix<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> lambda)
        {
            Func<Func<Func<T, TResult>, Func<T, TResult>>, Func<T, TResult>>
            y = f => ((Recursive<T, TResult>)(g => x => f(g(g))(x)))
                     ((Recursive<T, TResult>)(g => x => f(g(g))(x)));
            return y(lambda);
        }

        static void ForEach<T>(this IEnumerable<T> src, action)
        {
            foreach (T item in src) { action(item); }
        }
    }
}

おお、不動点演算子でラムダでLINQでエラトステネスってますね!(日本語が変)
確かにY Combinatorはすごいアルゴリズム!すごい(面白い)よこれ。


ついでにY Combinatorの引数を増やしてみる

ついでなので、引数を増やしたバージョンのY Combinatorも投下しておきます。
(引数増やしてもY Combinatorと呼んでいいのかわかんないけど。)

        /// <summary>
        /// 2つの引数をとる Y Combinator
        /// </summary>
        delegate Func<T1, Recursive<T1,(Recursive<T1, f);
        static Func<T1, Fix<T1,(Func<Func<T1,,>> lambda)
        {
            Func<Func<Func<T1,,>>,>>
            y = f => ((Recursive<T1,)(g => (a1,(g))(a1,                  ((Recursive<T1,)(g => (a1,(g))(a1,          return y(lambda);
        }

        /// <summary>
        /// 3つの引数をとる Y Combinator
        /// </summary>
        delegate Func<T1, Recursive<T1,(Recursive<T1, f);
        static Func<T1, Fix<T1,(Func<Func<T1,,>> lambda)
        {
            Func<Func<Func<T1,,>>,>>
            y = f => ((Recursive<T1,)(g => (a1,(g(g))(a1,                    ((Recursive<T1,)(g => (a1,(g(g))(a1,            return y(lambda);
        }

        /// <summary>
        /// 4つの引数をとる Y Combinator
        /// </summary>
        delegate Func<T1,> Recursive<T1,>(Recursive<T1,> f);
        static Func<T1,> Fix<T1,>(Func<Func<T1,>,t>> lambda)
        {
            Func<Func<Func<T1,>,t>>,t>>
            y = f => ((Recursive<T1,>)(g => (a1,(g(g))(a1,                    ((Recursive<T1,>)(g => (a1,(g(g))(a1,            return y(lambda);
        }

とりあえず、書いてはみたものの。なんぞこれーw(Func自重)
書いてみて思いました。あまり現実的ではないな、と(笑)


まとめ
Y Combinatorすげー(面白い)って思ったし、不動点を用いてラムダで再帰を表現とかって、かなりCool!なんだけども。
基本的には、クールポコよろしく「モテようとして・・、Y Combinatorを使って再帰を書いているヤツがいたんですよ。
なーにぃ!やっちまったなッ!男は黙って、普通に再帰。男は黙って、普通に再帰。」と思う次第。
C#に限って言えば、普通に再帰を書くという選択肢を選ぶことの方が、どうも一般的な感じがしてしまう。*3
理解しちゃった人には問題ないんでしょうが、一般的にどうなんよ?ってゆー可読性の心配が残るのも事実。


結論:Y Combinator・・・、恐ろしい子!




(追記:2008/08/26)
なんか無駄にややこしく書いてましたね(^ω^;)

        ///// <summary>
        ///// Y Combinator
        ///// </summary>
        delegate Func<T, TResult> Recursive<T, TResult>(Recursive<T, TResult> f);
        static public Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> f)
        {
            Recursive<T, TResult> r = g => x => f(g(g))(x);
            return r(r); 
        } 

*1:つまるところ、匿名関数の再帰のこと。

*2:不動点オペレータとか、不動点コンビネータとも言うみたい。

*3:もちろん、匿名関数の再帰はY Combinatorの方が美しいけど。