Yコンビネータができるまで（C#）

Yコンビネータ復習 - テンポラリをC#で書いてみた。
再起呼び出しをちょびちょび書き換えるので結構長編です。
C＃だと静的型なので自己呼び出しするdelegateが必要。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Expressions;
namespace Y
{
    class Program
    {
        delegate int sum_delegate(int n);
        delegate sum_delegate fun_delegate(fun_delegate f);

        static void Main(string[] args)
        {
            int i = Fun(3);
            Console.WriteLine(i);
            Console.ReadKey();
        }

        static int Fun(int n)
        {
            if (n == 0)
            {
                return 0;
            }
            else
            {
                return n + Fun(n - 1);
            }
        }
    }
}

こんな感じの再帰関数をYコンビネータっぽいのを使って書き直す。
まずは再起呼び出しのFunを外からパラメータとして受け取るようにする。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Expressions;

namespace Y
{
    class Program
    {
        delegate FUNC SelfCaller<FUNC>(SelfCaller<FUNC> f);
        static void Main(string[] args)
        {
            int i = Fun(Fun)(3);
            Console.WriteLine(i);
            Console.ReadKey();
        }

        static Func<int, int> Fun(SelfCaller<Func<int, int>> fun)
        {
            return delegate(int n)
            {
                if (n == 0)
                {
                    return 0;
                }
                else
                {
                    return n + fun(fun)(n - 1);
                }
            };
        }
    }
}

こうなった。
つぎにFunをMakeFunに変えて、MakeFunを呼び出すラッパをFunにする。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Expressions;

namespace Y
{
    class Program
    {
        delegate FUNC SelfCaller<FUNC>(SelfCaller<FUNC> f);
        static void Main(string[] args)
        {
            int i = Fun()(3);
            Console.WriteLine(i);
            Console.ReadKey();
        }
        static Func<int, int> Fun()
        {
            return MakeFun(MakeFun);
        }
        static Func<int, int> MakeFun(SelfCaller<Func<int, int>> fun)
        {
            return delegate(int n)
            {
                if (n == 0)
                {
                    return 0;
                }
                else
                {
                    return n + fun(fun)(n - 1);
                }
            };
        }
    }
}

fun(fun)(n - 1)部分を切り出す。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Expressions;
namespace Y
{
    class Program
    {
        delegate FUNC SelfCaller<FUNC>(SelfCaller<FUNC> f);
        static void Main(string[] args)
        {
            int i = Fun()(3);
            Console.WriteLine(i);
            Console.ReadKey();
        }
        static Func<int, int> Fun()
        {
            return MakeFun(MakeFun);
        }

        static Func<int, int> MakeFun(SelfCaller<Func<int, int>> fun)
        {
            return delegate(int n)
            {
                Func<int, int> imple = delegate(int m)
                {
                    return fun(fun)(m);
                };
                if (n == 0)
                {
                    return 0;
                }
                else
                {
                    return n + imple(n - 1);
                }
            };
        }
    }
}
||>

実処理を外から受けとるようにする。
static Func<int, int> Imple(Func<int, int> fun)が実際の処理。
>|cs|
&#65279;using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Expressions;
namespace Y
{
    class Program
    {

        delegate FUNC SelfCaller<FUNC>(SelfCaller<FUNC> f);

        static void Main(string[] args)
        {
            int i = Fun()(3);
            Console.WriteLine(i);
            Console.ReadKey();
        }
        static Func<int, int> Fun()
        {
            return MakeSelfCaller(Imple)(MakeSelfCaller(Imple));
        }
        static SelfCaller<Func<int, int>> MakeSelfCaller(Func<Func<int, int>, Func<int, int>> imple) 
        {
            return delegate(SelfCaller<Func<int, int>> caller)
            {
                Func<int, int> makeFun = delegate(int m)
                {
                    return caller(caller)(m);
                };
                return imple(makeFun);
            };
        }
        static Func<int, int> Imple(Func<int, int> fun)
        {
            return delegate(int n)
            {
                if (n == 0)
                {
                    return 0;
                }
                else
                {
                    return n + fun(n - 1);
                }
            };
        }
    }
}

FunがImpleをとるようにして、FunをYに改名。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Expressions;
namespace Y
{
    class Program
    {
        delegate FUNC SelfCaller<FUNC>(SelfCaller<FUNC> f);
        static void Main(string[] args)
        {
            int i = Y(Imple)(3);
            Console.WriteLine(i);
            Console.ReadKey();
        }
        static Func<int, int> Y(Func<Func<int,int>,Func<int,int>> imple)
        {
            return MakeSelfCaller(imple)(MakeSelfCaller(imple));
        }
        static SelfCaller<Func<int, int>> MakeSelfCaller(Func<Func<int, int>, Func<int, int>> imple)
        {
            return delegate(SelfCaller<Func<int, int>> caller)
            {
                Func<int, int> makeFun = delegate(int m)
                {
                    return caller(caller)(m);
                };
                return imple(makeFun);
            };
        }
        static Func<int, int> Imple(Func<int, int> fun)
        {
            return delegate(int n)
            {
                if (n == 0)
                {
                    return 0;
                }
                else
                {
                    return n + fun(n - 1);
                }
            };
        }
    }
}

SelfCallerをインラインに展開してしまう。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Expressions;
namespace Y
{
    class Program
    {
        delegate FUNC SelfCaller<FUNC>(SelfCaller<FUNC> f);
        static void Main(string[] args)
        {
            int i = Y(Imple)(3);
            Console.WriteLine(i);
            Console.ReadKey();
        }
        static Func<int, int> Y(Func<Func<int, int>, Func<int, int>> imple)
        {
            Func<Func<Func<int, int>, Func<int, int>>, SelfCaller<Func<int, int>>> caller =
                delegate(Func<Func<int, int>, Func<int, int>> prmImple)
                {
                    return delegate(SelfCaller<Func<int, int>> prmCaller)
                    {
                        Func<int, int> makeFun = delegate(int m)
                    {
                        return prmCaller(prmCaller)(m);
                    };
                        return prmImple(makeFun);
                    };
                };
            return caller(imple)(caller(imple));
        }
        static Func<int, int> Imple(Func<int, int> fun)
        {
            return delegate(int n)
            {
                if (n == 0)
                {
                    return 0;
                }
                else
                {
                    return n + fun(n - 1);
                }
            };
        }
    }
}

Impleは消しちゃって、Lambda式を受けとるように変更。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Expressions;
namespace Y
{
    class Program
    {
        delegate FUNC SelfCaller<FUNC>(SelfCaller<FUNC> f);
        static void Main(string[] args)
        {
            int i = Y(f => n =>
            {
                if (n == 0)
                {
                    return 0;
                }
                else
                {
                    return n + f(n - 1);
                }
            })(3);
            Console.WriteLine(i);
            Console.ReadKey();
        }
        static Func<int, int> Y(Func<Func<int, int>, Func<int, int>> imple)
        {
            Func<Func<Func<int, int>, Func<int, int>>, SelfCaller<Func<int, int>>> caller =
                delegate(Func<Func<int, int>, Func<int, int>> prmImple)
                {
                    return delegate(SelfCaller<Func<int, int>> prmCaller)
                    {
                        Func<int, int> makeFun = delegate(int m)
                        {
                            return prmCaller(prmCaller)(m);
                        };
                        return prmImple(makeFun);
                    };
                };
            return caller(imple)(caller(imple));
        }
    }
}

intにしてた型をT、TResultに戻す。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Expressions;
namespace Y
{
    class Program
    {
        delegate FUNC SelfCaller<FUNC>(SelfCaller<FUNC> f);
        static void Main(string[] args)
        {
            int i = Y<int,int>(f => n =>
            {
                if (n == 0)
                {
                    return 0;
                }
                else
                {
                    return n + f(n - 1);
                }
            })(3);
            Console.WriteLine(i);
            Console.ReadKey();
        }
        static Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> imple)
        {
            Func<Func<Func<T, TResult>, Func<T, TResult>>, SelfCaller<Func<T, TResult>>> caller =
                delegate(Func<Func<T, TResult>, Func<T, TResult>> prmImple)
                {
                    return delegate(SelfCaller<Func<T, TResult>> prmCaller)
                    {
                        Func<T, TResult> makeFun = delegate(T m)
                        {
                            return prmCaller(prmCaller)(m);
                        };
                        return prmImple(makeFun);
                    };
                };
            return caller(imple)(caller(imple));
        }
    }
}

あとはちょこちょこと整える。
わかりやすいようにdelegateで書いてる部分をLambdaに置き換えていく。
最終的にはこんな感じ。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Expressions;
namespace Y
{
    class Program
    {
        delegate FUNC SelfCaller<FUNC>(SelfCaller<FUNC> f);
        static void Main(string[] args)
        {
            string s1 = Y<int,string>(f => n =>
            {
                if (n == 0)
                {
                    return "0";
                }
                else
                {
                    return n.ToString() + f(n - 1);
                }
            })(3);
            Console.WriteLine(s1);
            string s2 = Y<int, int, string>(f => (n, m) =>
                {
                    if (n == 0)
                    {
                        return "0";
                    }
                    else
                    {
                        return n.ToString() + ":" + m + ":" + f(n - 1, m);
                    }
                })(3, 4);
            Console.WriteLine(s2);
            Console.ReadKey();
        }
        static Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> imple)
        {
            Func<Func<Func<T, TResult>, Func<T, TResult>>, SelfCaller<Func<T, TResult>>> caller =
                prmImple => prmCaller => prmImple(m => prmCaller(prmCaller)(m));
            return caller(imple)(caller(imple));
        }
        static Func<T1, T2, TResult> Y<T1, T2, TResult>(Func<Func<T1, T2, TResult>, Func<T1, T2, TResult>> imple)
        {
            Func<Func<Func<T1, T2, TResult>, Func<T1, T2, TResult>>, SelfCaller<Func<T1, T2, TResult>>> caller =
                prmImple => prmCaller => prmImple((a,b) => prmCaller(prmCaller)(a,b));
            return caller(imple)(caller(imple));
        }
    }
}