ラムダとY Combinatorと私。Y Combinatorは恐ろしい子。
再帰的な関数を作る場合に、その関数に名前をつけずに定義するにはどうすればよいの？*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ってなんぞや？って方はぜひご一読を。
(タイトルも洒落がきいてて素敵ですｗ)
C#のラムダ式でY Combinatorを書いてみる
/// <summary> /// Y Combinatorみたいなやつ /// </summary> static Func<T,Fix<T,Func<Func<T,>> F) { return t => F(Fix(F))(t); }
確かにこの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); }
とりあえず、書いてはみたものの。なんぞこれーｗ(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);
}
