Hello World
Spiga

使用Lambda表达式编写递归函数

2009-08-31 01:40 by 老赵, 12638 visits

其实这从来不是一个很简单的事情,虽然有些朋友认为这很简单。

伪递归

我的意思是,某些看上去像递归的做法,事实上并非是递归,所以我把它叫做是“伪”递归。

例如,我们想要使用Lambda表达式编写一个计算递归的fac函数,一开始我们总会设法这样做:

Func<int, int> fac = x => x <= 1 ? 1 : x * fac(x - 1);

不过此时编译器会无情地告诉我们,fac还没有定义。于是您可能会想,这个简单,分两行写咯。于是有朋友就会给出这样的代码:

Func<int, int> fac = null;
fac = x => x <= 1 ? 1 : x * fac(x - 1);

这样看起来也很“递归”,执行起来似乎也没有问题。但是,其实这并没有使用Lambda表达式构造一个递归函数,为什么呢?因为我们使用Lambda表达式构造的其实只是一个普通的匿名方法,它是这样的:

x => x <= 1 ? 1 : x * fac(x - 1);

既然是“匿名方法”,这个构造的东西是没有名字的——因此用Lambda表达式写递归“从来不是一个很简单的事情”。那么这个Lambda表达式里的fac是什么呢?是一个“委托”。因此,这只是个“调用了一个委托”的Lambda表达式。“委托对象”和“匿名方法”是有区别的,前者是一个实际的对象,而后者只是个“定义方式”,只是“委托对象”可以成为“匿名方法”的载体而已。这个Lambda表达式构造的“委托对象”在调用时,它会去寻找fac这个引用所指向的委托对象。请注意,这里是根据“引用”去找“对象”,这意味着Lambda表达式构造的委托对象在调用时,fac可能已经不再指向当初的委托对象了。例如:

Func<int, int> fac = null;
fac = x => x <= 1 ? 1 : x * fac(x - 1);
Console.WriteLine(fac(5)); // 120;

Func<int, int> facAlias = fac;
fac = x => x;
Console.WriteLine(facAlias(5)); // 20

第一次打印出的120是正确的结果。不过facAlias从fac那里“接过”了使用Lambda表达式构造的委托对象之后,我们让fac引用指向了新的匿名方法x => x。于是facAlias在调用时:

facAlias(5)     <— facAlias是x => x <= 1 ? 1 : x * fac(x – 1)
= 5 <= 1 ? 1 : 5 * fac(5 - 1)
= 5 * fac(4)    <— 注意此时fac是x => x
= 5 * 4
= 20

自然就不对了。

因此,使用Lambda表达式构造一个递归函数不是一件容易的事情。

把自己传给自己吧

可能已经有朋友知道“标准”的做法是什么样的,不过我这里还想谈一下我当时遇到这个问题时想到的一个做法。比较笨(非常符合我的特点),但是可以解决问题。

我的想法是,既然使用“Lambda表达式来构造一个递归函数”的难点是因为“我们正在构造的东西是没有名字的”,因此“我们无法调用自身”。那么,如果我们换种写法,把我们正在调用的匿名函数作为参数传给自己,那么不就可以在匿名函数的方法体中,通过调用参数来调用自身了吗?于是,原本我们构造fac方法的Lambda表达式:

x => x <= 1 ? 1 : x * fac(x - 1);

就需要变成:

(f, x) => x <= 1 ? 1 : x * f(f, x - 1);

请注意,这里的f参数是一个函数,它也是我们正在使用Lambda表达式定义的匿名委托(就是“(f, x) => ...”这一长串)。为了递归调用,它还必须把自身作为第一个参数传入下一层的调用中去,所以最后不是fac(x - 1)而是f(f, x - 1)。我们可以把这个匿名函数放到一个叫做selfFac的变量中去:

var selfFac = (f, x) => x <= 1 ? 1 : x * f(f, x - 1);

在第一次调用selfFac时,我们必须把它自身传递进去。于是我们可以这样来获得阶乘的结果:

Console.WriteLine(selfFac(selfFac, 5)); // 120;

但是这段代码没法编译通过,因为编译器不知道selfFac应该是什么类型的委托对象。不过根据selfFac(selfFac, 5)的调用方式,我们可以推断出,这个委托类型会接受两个参数,第一个是它自身的类型,第二个是个整型,而返回的也是个整型。于是,我们可以得出委托的签名了:

delegate int SelfFactorial(SelfFactorial selfFac, int x);

哎,但是这一点都不通用啊。没关系,我们可以写的通用一些:

delegate TResult SelfApplicable<T, TResult>(SelfApplicable<T, TResult> self, T arg);

这样,我们便可以定义selfFac,甚至于selfFib(菲波纳契数列):

SelfApplicable<int, int> selfFib = (f, x) => x <= 1 ? 1 : f(f, x - 1) + f(f, x - 2);
Console.WriteLine(selfFib(selfFib, 5)); // 8

但是,这还不是我们所需要的递归函数啊。没错,我们需要的是传入一个x就可以得到结果的函数,这种每次还需要把自己传进去的东西算什么?不过这个倒也容易,在selfXxx的基础上再前进一步就可以了:

SelfApplicable<int, int> selfFac = (f, x) => x <= 1 ? 1 : x * f(f, x - 1);
Func<int, int> fac = x => selfFac(selfFac, x);

SelfApplicable<int, int> selfFib = (f, x) => x <= 1 ? 1 : f(f, x - 1) + f(f, x - 2);
Func<int, int> fib = x => selfFib(selfFib, x);

为此,我们甚至可以总结出一个辅助方法:

static Func<T, TResult> Make<T, TResult>(SelfApplicable<T, TResult> self)
{
    return x => self(self, x);
}

于是乎:

var fac = Make<int, int>((f, x) => x <= 1 ? 1 : x * f(f, x - 1));
var fib = Make<int, int>((f, x) => x <= 1 ? 1 : f(f, x - 1) + f(f, x - 2));

这样我们便使用Lambda表达式定义了递归函数。当然,需要两个参数的递归函数定义方式也比较类似。首先是SelfApplicable委托类型和对应的辅助方法:

// 委托类型
delegate TResult SelfApplicable<T1, T2, TResult>(SelfApplicable<T1, T2, TResult> self, T1 arg1, T2 arg2);

// 辅助方法
static Func<T1, T2, TResult> Make<T1, T2, TResult>(SelfApplicable<T1, T2, TResult> self)
{
    return (x, y) => self(self, x, y);
}

于是使用“辗转相除法”计算最大公约数的gcd函数便是:

var gcd = Make<int, int, int>((f, x, y) => y == 0 ? x : f(f, y, x % y));
Console.WriteLine(gcd(20, 36)); // 4

这也是我目前凭“个人能力”能够走出的最远距离了。

不动点组合子

但是装配脑袋很早给了我们更好的解决方法:

static Func<T, TResult> Fix<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> f)
{
    return x => f(Fix(f))(x);
}

static Func<T1, T2, TResult> Fix<T1, T2, TResult>(Func<Func<T1, T2, TResult>, Func<T1, T2, TResult>> f)
{
    return (x, y) => f(Fix(f))(x, y);
}

Fix求出的是函数f的不动点,它就是我们所需要的递归函数:

var fac = Fix<int, int>(f => x => x <= 1 ? 1 : x * f(x - 1));
var fib = Fix<int, int>(f => x => x <= 1 ? 1 : f(x - 1) + f(x - 2));
var gcd = Fix<int, int, int>(f => (x, y) => y == 0 ? x : f(y, x % y));

用脑袋的话来说,Fix方法应该被视为是内置方法。您比较Fix方法内部和之前的Make方法内部的写法,就能够意识到两种做法之间的差距了。

由于我的脑袋不如装配脑袋的脑袋装配的那么好,即使看来一些推导过程之后还是无法做到100%的理解,我还需要阅读更多的内容。希望在以后的某一天,我可以把这部分内容融会贯通地理解下来,并且可以详细地解释给大家听。在这之前,我还是听脑袋的话,把Fix强行记在脑袋里吧。

最后,希望大家多多参与一些如“函数式链表快速排序”这样的趣味编程——不过,千万不要学脑袋这样做:

var qsort = Fix<IEnumerable<int>, IEnumerable<int>>(f => l => l.Any() ? f(l.Skip(1).Where(e => e < l.First())).Concat(Enumerable.Repeat(l.First(), 1)).Concat(f(l.Skip(1).Where(e => e >= l.First()))) : Enumerable.Empty<int>());

当然,偶尔玩玩是有益无害的。

所属话题:“伪”递归
Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

71 条回复

  1. Xuefly
    *.*.*.*
    链接

    Xuefly 2009-08-31 01:50:00

    占个沙发

  2. Arthraim
    *.*.*.*
    链接

    Arthraim 2009-08-31 02:15:00

    天书一般,C#代码被你玩在手掌之中啊,设计lambda表达式的时候估计死也不会想着有人写得出这样的代码,佩服佩服……

  3. Nick Wang (懒人王)
    *.*.*.*
    链接

    Nick Wang (懒人王) 2009-08-31 02:26:00

    对于看不懂的代码无爱,就不仔细看了

  4. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-31 03:55:00

    @Jeffrey Zhao
    基本上你的Make拿来curry一下就跟Y组合子的其中一步(y(y))差不多了,吧?
    装配脑袋在前面那帖的回复里给的Fix是利用了语言本身提供的递归而写的,所以要从“纯”的角度上说还是有点作弊。当然脑袋早就知道别的做法了,只不过那样写Fix确实方便大家理解些 ^ ^
    对单参数的递归函数,用C#记法来写,忽略类型声明的话,这样:

    var Y = (y => y(y))(y => f => x => f(y(y)(f))(x));
    

    老赵的self(self, x)跟这里的y(y)是不是很像呢?留意到这里没有用到语言内建的方法递归(但是用了语言内建的类型递归)。
    要写得那么麻烦是因为C#的求值是eager的,不这么写就无限递归了。

    要说的话,其实跟Omega可能更像些?如果忽略类型声明的话,用C#记法写Omega组合子就是:
    var omega = f => f(f);
    

    那omega的类型是什么呢?还是得用到那个神奇的SelfAppicable<TFunc>。看看这个:
    using System;
    
    namespace TestOmega {
        delegate T SelfApplicable<T>( SelfApplicable<T> f );
    
        static class Program {
            static void Main( string[ ] args ) {
                SelfApplicable<Func<int, int>> omega = f => f( f );
                SelfApplicable<Func<int, int>> _fac = f => x => x <= 1 ? 1 : x * f( f )( x - 1 );
                Func<int, int> factorial = x => omega( _fac )( x );
                Console.WriteLine( factorial( 5 ) );
            }
        }
    }
    

    我把几个lambda拆开了写了,免得写在一行太长难读。实际上最终的factorial完全可以串起来写:(省略类型声明)
    n => (f => f(f))(f => x => x <= 1 ? 1 : x * f(f)(x - 1))(n)
    

    不过要编译通过的话还是得在中间插入类型,所以还是算了……

    不想用古怪的SelfAppicable的话,可以用别的办法绕开类型的限制。借用前面的泛型那帖中回帖的代码,
    using System;
    
    namespace TestCSharp4Dynamic {
        static class Omega<T> {
            public static readonly Func<Func<dynamic,T>,T> Instance = f => f(f);
        }
    
        static class Program {
            static void Main(string[] args) {
                var omega = Omega<Func<int, int>>.Instance;
                var fac = (Func<int, int>)(n => omega(f => x => x <= 1 ? 1 : x * f(f)(x - 1))(n));
                var fac5 = fac(5);
                Console.WriteLine(fac5); // 120
            }
        }
    }
    

    在C# 4.0里就可以这么做。有兴趣的同学可以在Visual Studio 2010 Beta 1里试试,或者只要装.NET Framework 4.0 Beta 1然后用里面的C#编译器也行。

    这玩儿搅多了能把脑汁都搅出来……||||
    无类型的lambda演算怎么玩都可以,甚至能玩出悖论。有类型之后事情就被限制住了。上面的C#代码虽然可以在函数里回避显式的递归,但为了描述函数的类型,在类型声明里还是让递归冒了出来。如果只让用Func系的委托来描述函数类型,并且不让用dynamic的话,C#要如何写这些组合子出来呢……
    强调用Func系的委托是因为它们就跟一般写函数类型里的“->”一样。Func<int, int>就是int -> int。其实int -> int跟x => x一样,都是匿名的。要用匿名函数表达递归的话,在类型的一侧肯定也需要同等的“运算能力”。用SelfApplicable<TFunc>始终是个作弊,呵呵~

  5. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-08-31 07:59:00

    55,被当做反面教材了……

  6. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-08-31 08:11:00

    @RednaxelaFX

    你应该再看看我用VB(2008)写出的那个Lambda表达式。。在那个文章里,我写出的最后一个Y实现里VB做了一项非常聪明的隐式类型转换,完全同样的代码我即使翻译成C#4的dynamic也不能编译通过。目前我也没有完全参透,呵呵。我还没发现不用SelfApplicable,使C#也作出那个类型转换的能力(肯定是可以,只是不能生搬硬套)。

    其实要说也不复杂,就是VB会自动将Func(Of Object, T)转换成Func(Of Func(Of Object, T), T)来使用。

  7. Selfocus
    *.*.*.*
    链接

    Selfocus 2009-08-31 08:45:00

    我就看看~~~

  8. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-31 08:48:00

    @装配脑袋
    喔,VB居然还会做这种转换……果然即便加入了dynamic,C# 4.0在迟绑定和隐式转换之类的规定上跟VB还是有很多不同。我不会VB(逃……
    lambda演算和各种组合子我不太熟,连wiki都还吃完,只能充充胖子而已。有几本关于类型系统的书一直想读也还没动手,诶。我是猜如果想“不作弊”去写出带类型的lambda演算的递归,那么“匿名函数的匿名类型”也应该要有相应的不通过名字而引入递归的方法。接受类型然后生产出类型,甚至能表达无限的概念,或许是高阶类型能达到的效果?

  9. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-31 08:55:00

    @装配脑袋

    装配脑袋:55,被当做反面教材了……


    我没有想拿脑袋来做反面教材啦……|||| 只是把你也知道的回字的另外几种写法拉出来溜了溜而已 =v=

  10. rexzhou[未注册用户]
    *.*.*.*
    链接

    rexzhou[未注册用户] 2009-08-31 09:12:00

    最近很流行Lambda表达式啊,其实Y组合子用Lua JavaScript Python Scheme很容易的写,甚至VB.NET也可以,但是C#一直都不够漂亮,因为C#必须要声明变量类型的关系,而var关键字又不能用来引用Lambda表达式。无奈

  11. 老赵
    admin
    链接

    老赵 2009-08-31 09:15:00

    @rexzhou
    你说的没错,Haskell,Erlang,F#也容易……
    不过C#的Lambda表达式写起来是最漂亮的,不需要lambda,Function,function,fun这些关键字,赫赫。

  12. 老赵
    admin
    链接

    老赵 2009-08-31 09:15:00

    @RednaxelaFX
    基本上你的Make拿来curry一下就跟Y组合子的其中一步(y(y))差不多了,吧?


    我也觉得有些接近,但是我就是没法再前进一步了。一会儿仔细看看你写的。
    其实我引用的那个文章里是有过程的,只是有一个小坎还没有完全过去。
    它定义了Y Combinator没有用语言内置功能,不过它也说了,实际上最有用的做法就是这种Fix写法。
    我的方法也没有利用到语言内置功能,而且最容易理解,所以适合让我这种脑子想出来……

  13. 老赵
    admin
    链接

    老赵 2009-08-31 09:17:00

    Arthraim:天书一般,C#代码被你玩在手掌之中啊,设计lambda表达式的时候估计死也不会想着有人写得出这样的代码,佩服佩服……


    你太小看语言设计者了,这些对他们来说都是平时休息时玩玩的……

  14. japhie
    *.*.*.*
    链接

    japhie 2009-08-31 09:20:00

    老赵的奉献精神是没的说的了!疯狂顶他!

  15. 麒麟.NET
    *.*.*.*
    链接

    麒麟.NET 2009-08-31 09:31:00

    这个……完全看不懂啊

  16. 没事找事[未注册用户]
    *.*.*.*
    链接

    没事找事[未注册用户] 2009-08-31 09:45:00

    函数直接或间接调用自身称为递归,
    函数通过函数指针调用自身就不是递归了??
    虽然函数指针的指向有可能被改变,
    但在它没被改变的时候毫无疑问就是递归.

  17. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-31 09:46:00

    @Jeffrey Zhao
    Mads那篇blog我也来来回回读过很多次了,花了很长时间才勉强记住了“形”而已,“神”恐怕还是没得要领 T T
    所以我主要记的用于C#的SelfApplicable<TFunc>和Y = y => f => x => f(y(y)(f))(x)也是从Mads那篇来的。只不过后来发觉Y(Y)可以跟前面的合在一起写而已。

  18. 陛下
    *.*.*.*
    链接

    陛下 2009-08-31 09:46:00

    嗯,看来还是写两行好,不用废脑细胞去读、去绕。简单就是美,玩成这样偶尔感觉像是金庸笔下的偏侠练通了某门歪功,呵呵。牛逼的是,居然不走火入魔!
    老赵有空多给咱讲讲架构方面的课(或者我没关注漏掉了?),如何从全局着眼架构、设计一个系统。
    个人期望啊,呵呵。

  19. 老赵
    admin
    链接

    老赵 2009-08-31 09:47:00

    @没事找事
    那么你只能说,它产生了递归的效果,执行方法指针就不是递归了,无论变没变。
    但是递归的定义就是自己调用自己,不是执行一个委托对象。
    当然,我这篇文章写得是理论,实际使用过程中你可以不必严格按照定义来。

  20. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-31 10:07:00

    @Jeffrey Zhao

    Jeffrey Zhao:
    @没事找事
    那么你只能说,它产生了递归的效果。
    但是递归的定义就是自己调用自己,不是执行一个委托对象。
    当然,我这篇文章写得是理论,实际使用过程中你可以不必严格按照定义来。


    或许用值的“绑定时间”来解释这个问题比较容易理解些?
    把这个:
    Func<int, int> fac = null;              // fac的绑定(1)
    fac = x => x <= 1 ? 1 : x * fac(x - 1); // fac的绑定(2);lambda里的fac暂时还在用绑定(1)
    fac(5); // 使用fac的绑定(2)
    

    跟这个比较:(为简洁忽略中间的类型)
    var omega = f =>     // f的绑定(1)
                    f(f) // 使用f的绑定(1)
    /////////
    var fac = 
        f =>                                // f的绑定(1)
            x => x <= 1 ? 1 : x * f(x - 1); // 使用f的绑定(1)
    

    在所谓“真正的递归”中,整个表达式的所有值都是“已绑定”的;在所谓“伪递归”中,例子里的fac = null可以理解为fac的一种“未绑定”状态,在定义fac的真正内容时引用的也是“未绑定”状态,所以“不纯”。
    在lambda箭头左边出现的内容(参数),到了右边就是“已绑定”的。赋值运算符的特征却不是这样,左边的名字在右边处于“尚未绑定”的状态。

    这种问题要是转换为静态单赋值形式来看的话甚好理解……

  21. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-08-31 10:24:00

    吐槽

    脑袋那样的写法一向不是玩程序 是玩我们的

    以上

  22. rexzhou[未注册用户]
    *.*.*.*
    链接

    rexzhou[未注册用户] 2009-08-31 10:32:00

    韦恩卑鄙:
    吐槽

    脑袋那样的写法一向不是玩程序 是玩我们的

    以上


    其实有数学上的美感,Y组合子的原来定义(附Lua实现,但是实现Lambda函数不够漂亮,需要function、return和end):
    -- Y = λf·(λx·f (x x)) (λx·f (x x))

    local Y =
    function (F)
    return (function (x)
    return F(function (y) return (x(x))(y) end)
    end)(function (x)
    return F(function (y) return (x(x))(y) end)
    end)
    end

    local FactGen =
    function (fact)
    return (function(n)
    if n == 0 then
    return 1
    else
    return n * fact(n - 1)
    end
    end)
    end

    print((Y(FactGen))(10))

  23. 斯克迪亚
    *.*.*.*
    链接

    斯克迪亚 2009-08-31 10:52:00

    老赵真会玩:)

  24. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-08-31 11:03:00

    @rexzhou
    我针对的是这一段


    var qsort = Fix<IEnumerable<int>, IEnumerable<int>>(f => l => l.Any() ? f(l.Skip(1).Where(e => e < l.First())).Concat(Enumerable.Repeat(l.First(), 1)).Concat(f(l.Skip(1).Where(e => e >= l.First()))) : Enumerable.Empty<int>());  

  25. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-31 11:14:00

    @韦恩卑鄙

    韦恩卑鄙:
    @rexzhou
    我针对的是这一段


    var qsort = Fix<IEnumerable<int>, IEnumerable<int>>(f => l => l.Any() ? f(l.Skip(1).Where(e => e < l.First())).Concat(Enumerable.Repeat(l.First(), 1)).Concat(f(l.Skip(1).Where(e => e >= l.First()))) : Enumerable.Empty<int>());  


    老赵的版本核心部分也是这样的形式啊……只是不是针对IEnumerable<int>而已

    Jeffrey Zhao:
    这是我写的:

    public static ImmutableList<T> QuickSort<T>(this ImmutableList<T> list, Func<T, T, int> compare)
    { 
        if (list == null) throw new ArgumentNullException("list");
        if (compare == null) throw new ArgumentNullException("compare");
    
        return list.IsEmpty ? list : 
            list.Tail.Filter(e => compare(e, list.Head) < 0).QuickSort(compare) +
            ImmutableList<T>.Create(list.Head) +
            list.Tail.Filter(e => compare(e, list.Head) >= 0).QuickSort(compare);
    }
    


    IsEmpty <=> Any()
    list <=> l.First()
    list.Tail <=> l.Skip(1)
    Filter <=> Where
    + <=> Concat
    Create <=> Repeat(..., 1)
    ...

  26. 戏水
    *.*.*.*
    链接

    戏水 2009-08-31 11:27:00

    好复杂 ,好复杂 。 老赵此文目的是讲述如何用lambda表达式来做递归吗?

  27. 老赵
    admin
    链接

    老赵 2009-08-31 11:33:00

    @戏水
    是的。

  28. 老赵
    admin
    链接

    老赵 2009-08-31 11:33:00

    韦恩卑鄙:
    脑袋那样的写法一向不是玩程序 是玩我们的


    hmmm……其实很容易的,你没有仔细看而已。

  29. 老赵
    admin
    链接

    老赵 2009-08-31 11:34:00

    @RednaxelaFX
    list <=> l.First()


    小bug,应该是list.Head,嘿嘿。
    // 话说,估计只有你的脑袋可以像装配脑袋的脑袋装配的那么好了……

  30. 温景良(Jason)
    *.*.*.*
    链接

    温景良(Jason) 2009-08-31 11:36:00

    好是好,但是貌似不容易阅读

  31. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-08-31 11:51:00

    Jeffrey Zhao:

    韦恩卑鄙:
    脑袋那样的写法一向不是玩程序 是玩我们的


    hmmm……其实很容易的,你没有仔细看而已。


    看到"))))"就头疼

    我是连 f ( param1, param2)
    都要写成
    f
    (
    param1,
    param2
    )

    的阅读障碍者

  32. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-31 11:51:00

    @Jeffrey Zhao

    Jeffrey Zhao:

    @RednaxelaFX
    list <=> l.First()


    小bug,应该是list.Head,嘿嘿。
    // 话说,估计只有你的脑袋可以像装配脑袋的脑袋装配的那么好了……


    嗯bug了……我也原样quote了 T T
    // 装配脑袋以外的高手还没出来拍砖,我这一知半解的才冒出来混混……别说我谦虚,我真不懂。SKI组合子的运用也是找不到感觉,总是看到别人的解才觉得恍然大悟。虽然不懂,还是得蹭在帖里讨论讨论。把自己不知道的地方暴露出来等别人指正后正好学习,呵呵~

  33. 老赵
    admin
    链接

    老赵 2009-08-31 11:53:00

    @RednaxelaFX
    不错,和我一样是暴露狂,吸引高手来拍砖。

  34. 挑战激情
    *.*.*.*
    链接

    挑战激情 2009-08-31 13:05:00

    我记得pongba和g9也有相关内容的BLOG,算是对老赵你的这篇文章的补充啊。
    感谢老赵哈,让我可以从另一个角度来体验组合子

  35. 老赵
    admin
    链接

    老赵 2009-08-31 14:02:00

    @韦恩卑鄙
    你的代码一定很可怕……

  36. 铁打的西西。
    *.*.*.*
    链接

    铁打的西西。 2009-08-31 15:55:00

    @韦恩卑鄙
    ````

  37. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-08-31 16:42:00

    难看不是吹的
    三个月前写的一段。。。

                for (var i = 0; i < LayersCount; i++)
                {
                    var lyr = new LayerGroup(
                                                WingCount, PanelCreator,
                                                p =>
                                                {
                                                    if (PanelDecorator == null) PanelDecorator = Wall.DefaultPanelDecorator;
                                                    var tp = PanelDecorator.Invoke(p);
                                                    tp.Width = PanelWidth;
                                                    tp.Height = PanelHeigt;
                                                    return tp;
                                                },
                                                this, 
                                                LayersCount,
                                                 i 
                                            )
                    {
                        GlobalOffsetZ = GlobalZ - PanelSize.Width * i,
                        GlobalOffsetX = GlobalX,
                        GlobalOffsetY = GlobalY
            
    
                    };
                    Layers.Add(lyr);
                }
    

  38. winter-cn
    *.*.*.*
    链接

    winter-cn 2009-08-31 20:10:00

    看到不动点就头疼

  39. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-08-31 23:24:00

    终于看完了,没看评论,似乎就是一个定制的Y组合子么。

    Y组合子的纯粹形式:
    Y = g => (f=>g(f(f)))(f=>g(f(f))

    即,令h = g(f(f));
    则:Y = h(h)

    如果g(f)(x) = x <= 1 ? 1 : x * f(f, x - 1);
    其实就跟老赵的是一样的了。

  40. 老赵
    admin
    链接

    老赵 2009-08-31 23:27:00

    @Ivony...
    我搞不明白的就是如何从零推出Y组合子的,有个坎过不了。

  41. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-08-31 23:27:00

    RednaxelaFX:
    @Jeffrey Zhao
    Mads那篇blog我也来来回回读过很多次了,花了很长时间才勉强记住了“形”而已,“神”恐怕还是没得要领 T T
    所以我主要记的用于C#的SelfApplicable<TFunc>和Y = y => f => x => f(y(y)(f))(x)也是从Mads那篇来的。只不过后来发觉Y(Y)可以跟前面的合在一起写而已。



    Y组合子速记口诀:

    令西等于叽歪歪: c = y => g(y(y))
    西西就是不动点: Y = g => c(c)

  42. 老赵
    admin
    链接

    老赵 2009-08-31 23:29:00

    @Ivony...
    nb男啊。
    话说其实我也硬背下来了,不过希望你可以赶快把从头的推导过程写清楚……

  43. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-08-31 23:31:00

    刚才又想了想,似乎还是与Y组合子有区别的,笔记本没电了,算了。。。。

  44. Ivony...
    *.*.*.*
    链接

    Ivony... 2009-08-31 23:33:00

    Jeffrey Zhao:
    @Ivony...
    nb男啊。
    话说其实我也硬背下来了,不过希望你可以赶快把从头的推导过程写清楚……


    快了,明天就报到了,不动点算子应该是最后一个关口了,突破了这个就连起来了。

  45. 老赵
    admin
    链接

    老赵 2009-08-31 23:34:00

    @Ivony...
    有笔记本就是好。

  46. aaaaabbbbbb[未注册用户]
    *.*.*.*
    链接

    aaaaabbbbbb[未注册用户] 2009-09-01 09:37:00

    谢谢,受益匪浅

  47. EricWen
    *.*.*.*
    链接

    EricWen 2009-09-01 10:22:00

    var selfFac = (f, x) => x <= 1 ? 1 : x * f(f, x - 1);
    不能这么定义啊。
    报错:无法将“lambda 表达式”赋予隐式类型的局部

  48. Jeff Wong
    *.*.*.*
    链接

    Jeff Wong 2009-09-01 10:30:00

    这么好的帖子这么快就沉了?收藏。

  49. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-09-01 11:52:00

    @EricWen

    EricWen:
    var selfFac = (f, x) => x <= 1 ? 1 : x * f(f, x - 1);
    不能这么定义啊。
    报错:无法将“lambda 表达式”赋予隐式类型的局部


    只是说这么个意思而已。要编译通过的话得给出委托类型。老赵紧接着不是给出了SelfApplicable<T, TR>和可以编译通过的代码了么……

  50. 心远[未注册用户]
    *.*.*.*
    链接

    心远[未注册用户] 2009-09-01 23:28:00

    不好玩,很简单的事情弄这么复杂。老赵能不能多写点有实际价值的东东?

  51. 老赵
    admin
    链接

    老赵 2009-09-01 23:52:00

    @心远
    我只想说,看轻理论您很容易会吃苦的,我记录的这些都是我思考的过程。这东西如果真简单,也用不着数十年前的大师们研究那么多年了。
    我自大一句,您是不是只羡慕到我的技术,但是没有想想我是怎么从一无所知,一步一步走上来的?我乐于分享我的前进轨迹,而不是最终成果,您如果不愿意看的话,委屈您了。
    再者,我不知道最近我写的最多的ASP.NET MVC,算不算您口中“有实际价值的东西”?这足够算是“XX编程三百例”类型了吧?如果不是,很抱歉,我的项目真没有什么值得您学习的了。

  52. 星~无敌
    *.*.*.*
    链接

    星~无敌 2009-09-02 13:05:00

    没有用过,也看不懂

  53. CoolCode
    *.*.*.*
    链接

    CoolCode 2009-10-10 16:48:00

    今天看了脑袋的不动点,然后又来这里温故,不知道是不是我有点困了,感觉Lambda有一个容易引起歧义的地方(与以上文章无关):x => x <= 1
    当<=或者>=这些比较符出现时,=>和>=就容易混淆

  54. _lsp[未注册用户]
    *.*.*.*
    链接

    _lsp[未注册用户] 2009-10-12 13:11:00

    老赵,我测试了一下三种方式(递归,lambda伪递归,不动点递归)。 递归方式最快;lambda伪递归时间大约是递归的两倍。这很好理解,lamda伪递归用递归的方式创建了很多不同的匿名函数,调用这些匿名函数自然耗时。然而不懂点递归最耗时,远远远大于前两种方式。 这如何理解?

  55. 老赵
    admin
    链接

    老赵 2009-10-12 13:14:00

    @_lsp
    因为它创建的匿名函数最多,调用次数也最多咯。
    不过还好,复杂度是一样的。

  56. _lsp[未注册用户]
    *.*.*.*
    链接

    _lsp[未注册用户] 2009-10-12 13:26:00

    @Jeffrey Zhao
    对lamda函数一直很困惑,所以还有两个愚蠢的问题:
    1. 既然它创建很多的匿名函数,那么调用这些函数应该不是调用自己本身吧?那又如何成为“递归”?
    2. 同样是创建很多匿名函数,不动点相对伪递归的意义是什么?仅仅是为了实现真正的“递归”?

  57. 老赵
    admin
    链接

    老赵 2009-10-12 13:32:00

    @_lsp
    1、Fix是个辅助方法,创建的很多匿名函数也是为了辅助目的,它的作用是把一个函数A传递给自身,于是函数A就是个递归函数了。
    2、它的意义就是,比如有这么一个方法:Print(Func<int, int> func),如何向Print内传一个计算费波纳切数列的匿名函数?

  58. nop[未注册用户]
    *.*.*.*
    链接

    nop[未注册用户] 2009-10-13 11:31:00

    这个没名函数调用自己的事情交给StackTrace解决问题

  59. 老赵
    admin
    链接

    老赵 2009-10-13 11:37:00

    @nop
    啥?没听懂。

  60. ceee[未注册用户]
    *.*.*.*
    链接

    ceee[未注册用户] 2009-10-14 11:07:00

    太复杂了,没看懂

  61. PowerCoder
    *.*.*.*
    链接

    PowerCoder 2009-10-22 22:30:00

    不动点组合子变个形,可能会好理解些:
    static Func<T, TResult> Fix<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> f)
    {
    return x => f(Fix(f))(x);
    }

    static Func<T, TResult> Fix<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> f)
    {
    return x => f(Fix<T,TResult>(f))(x);
    }

    static Func<T, TResult> Fix<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> f)
    {
    Func<T,TResult> ff=f(Fix<T,TResult>(f));
    return x => ff(x);
    }

    static Func<T, TResult> Fix<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> f)
    {
    Func<T,TResult> ff= x => x <= 1 ? 1 : x*Fix<T,TResult>(f)(x - 1);
    return x=>ff(x);
    }

    static Func<T, TResult> Fix<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> f)
    {
    return x=>x <= 1 ? 1 : x * Fix<T,TResult>(f)(x - 1);
    }
    看最后个变形的这句Fix<T,TResult>(f)说明Fix就是在做Fix的递归运算

    所以个人理解是不动点组合子就是搭建好Lambda表达式的递归结构,然后将值x传如此递归结构从而计算出递归结果.

  62. jhkmnm
    123.65.224.*
    链接

    jhkmnm 2010-05-13 16:31:52

    看了头很大啊。。。。。

  63. We.小神
    112.94.191.*
    链接

    We.小神 2010-10-14 00:11:57

    赵老师我请问下这句

    Func<int, int> facAlias = fac;
    fac = x => x;
    

    是什么意思?

    我的理解是facAlias和fac都是指向同一个引用的委托,但下面这句话 fac = x => x; 就不是很明白,也不像把 x => x 加到委托链中。但是 fac += x => x; 这样得出的结果也是20。这句不明白,下面的看不下去了,赵老师您能抽空给像我这样的小菜解释一下吗?谢谢了~

  64. 老赵
    admin
    链接

    老赵 2010-10-14 13:20:38

    @We.小神

    fac = x => x
    

    等价于

    fac = new Func<int, int>(x => x)
    
  65. We.小神
    112.94.252.*
    链接

    We.小神 2010-10-14 19:54:31

    赵老师您好:

    一开始是:

    Func<int, int> fac = null;
    fac = x => x <= 1 ? 1 : x * fac(x - 1);
    

    接着 fac = x => x 后,facAlias 指向的应该也是 x => x 这个地址,那为什么 facAlias(5) 也会执行到 5 <= 1 ? 1 : 5 * fac(5 - 1) 这里?用 fac += x => x; 得到的结果也是20,您能跟我说说为什么吗,先谢谢了。本人悟性不高,您见笑了~

  66. 老赵
    admin
    链接

    老赵 2010-10-14 20:29:35

    @We.小神: 接着 fac = x => x 后,facAlias 指向的应该也是 x => x 这个地址

    谁跟你说的?基础中的基础啊。

  67. We.小神
    112.94.252.*
    链接

    We.小神 2010-10-15 00:24:06

    是呃,试了下原来真的不是指向同一个地址,有点懂,是自己基础不好,谢谢您的指点。

  68. earthengine
    112.213.196.*
    链接

    earthengine 2010-11-20 15:51:57

    以下代码是我苦心研究不动点组合子所得的成果,请评价一下。博主应该看得到我邮箱,希望多交流。

    using System;
    using System.Linq.Expressions;
    
    namespace LamdaUtil
    {
        public delegate R TFunc<R>(R i);
        public delegate R YFunc<R>(TFunc<R> i);
        public delegate R SFunc<R>(SFunc<R> i);
        public delegate R SFunc<T, R>(SFunc<T, R> i, T i1);
        public delegate Func<SFunc1<T>, T> SFunc1<T>(TFunc<T> i);
    
        public static class util
        {
            public static void Nop<T>(T o)
            {
            }
    
            #region ConvA -- Convert Actions to Func<T, R>
            public static Func<object, object> ConvA(Action a)
            {
                return x => a.DynamicInvoke();
            }
            public static Action ConvA<T, R>(Func<T, R> f, T x)
            {
                return () => f(x);
            }
            public static Func<T, object> ConvA<T>(Action<T> a)
            {
                return x => a.DynamicInvoke(x);
            }
            public static Action<T> ConvA<T, R>(Func<T, R> f)
            {
                return x => f(x);
            }
            public static Func<T1, Func<T2, object>> ConvA<T1, T2>(Action<T1, T2> a)
            {
                return x => y => a.DynamicInvoke(x, y);
            }
            public static Action<T1, T2> ConvA<T1, T2, R>(Func<T1, Func<T2, R>> f)
            {
                return (x, y) => f(x)(y);
            }
            public static Func<T1, Func<T2, Func<T3, object>>> ConvA<T1, T2, T3>(Action<T1, T2, T3> a)
            {
                return x => y => z => a.DynamicInvoke(x, y, z);
            }
            public static Action<T1, T2, T3> ConvA<T1, T2, T3, R>(Func<T1, Func<T2, Func<T3, R>>> f)
            {
                return (x, y, z) => f(x)(y)(z);
            }
            #endregion
    
            #region ConvF -- Convert Func(s) to Func<T, R> (convertion for Func<T, R> can be used to apply lamda expressions to another)
            public static Func<object, R> ConvF<R>(Func<R> f)
            {
                return x => f();
            }
            public static Func<R> ConvF<T, R>(Func<T, R> f, T x)
            {
                return () => f(x);
            }
            public static Func<T, R> ConvF<T, R>(Func<T, R> f)
            {
                return x => f(x);
            }
            public static Func<T1, Func<T2, R>> ConvF<T1, T2, R>(Func<T1, T2, R> f)
            {
                return x => y => f(x, y);
            }
            public static Func<T1, T2, R> ConvF<T1, T2, R>(Func<T1, Func<T2, R>> f)
            {
                return (x,y) => f(x)(y);
            }
            public static Func<T1, Func<T2, Func<T3, R>>> ConvF<T1, T2, T3, R>(Func<T1, T2, T3, R> f)
            {
                return x => y => z => f(x, y, z);
            }
            public static Func<T1, T2, T3, R> ConvF<T1, T2, T3, R>(Func<T1, Func<T2, Func<T3, R>>> f)
            {
                return (x, y, z) => f(x)(y)(z);
            }
            #endregion
    
            #region TConvA -- Convert TFunc<Action> to TFunc<Func<T, R>>
            public static TFunc<Func<object, object>> TConvA(TFunc<Action> af)
            {
                return f => x => af(() => f(null)).DynamicInvoke();
            }
            public static TFunc<Func<T, object>> TConvA<T>(TFunc<Action<T>> af)
            {
                return f => x => af(y => f(y)).DynamicInvoke(x);
            }
            public static TFunc<Func<T1, Func<T2, object>>> TConvA<T1, T2>(TFunc<Action<T1, T2>> af)
            {
                return f => x => y => af((xx, yy) => f(xx)(yy)).DynamicInvoke(x, y);
            }
            public static TFunc<Func<T1, Func<T2, Func<T3, object>>>> TConvA<T1, T2, T3>(TFunc<Action<T1, T2, T3>> af)
            {
                return f => x => y => z => af((xx, yy, zz) => f(xx)(yy)(zz)).DynamicInvoke(x, y, z);
            }
            #endregion
    
            #region TConvF -- Convert TFunc<Func> to TFunc<Func<T, R>>
            public static TFunc<Func<object, R>> TConvF<R>(TFunc<Func<R>> f)
            {
                return g => x => f(() => g(null))();
            }
            public static TFunc<Func<T, R>> TConvF<T, R>(TFunc<Func<T, R>> f)
            {
                return g => x => f(y => g(y))(x);
            }
            public static TFunc<Func<T1, Func<T2, R>>> TConvF<T1, T2, R>(TFunc<Func<T1, T2, R>> f)
            {
                return g => x => y => f((xx, yy) => g(xx)(yy))(x, y);
            }
            public static TFunc<Func<T1, Func<T2, Func<T3, R>>>> TConvF<T1, T2, T3, R>(TFunc<Func<T1, T2, T3, R>> f)
            {
                return g => x => y => z => f((xx, yy, zz) => g(xx)(yy)(zz))(x, y, z);
            }
            #endregion
        }
    
        public class Fix
        {
            public static Func<T, R> FixDirect<T, R>(TFunc<Func<T, R>> f)
            {
                return x => f(FixDirect(f))(x);
            }
            public static Func<T, R> Y<T, R>(TFunc<Func<T, R>> f)
            {
                return util.ConvF<SFunc<Func<T, R>>, Func<T, R>>
                    (t => f(t(t)))(t => x => f(t(t))(x));
            }
            public static Func<T, R> Y1<T, R>(TFunc<Func<T, R>> f)
            {
                return util.ConvF<SFunc1<Func<T, R>>, YFunc<Func<T, R>>>
                    (x => y => x(y)(x))(y => x => z => y(x(y)(x))(z))(f);
            }
            public static Func<T, R> Turing<T, R>(TFunc<Func<T, R>> f)
            {
                return util.ConvF<SFunc<YFunc<Func<T, R>>>, YFunc<Func<T, R>>>
                    (x => y => z => y(x(x)(y))(z))(x => y => z => y(x(x)(y))(z))(f);
            }
        }
    
        public static class FixExp<T, R>
        {
            public static readonly Expression<YFunc<Func<T, R>>> YExp = f => util.ConvF<SFunc<Func<T, R>>, Func<T, R>>
                (t => f(t(t)))(t => x => f(t(t))(x));
    
            public static readonly Expression<YFunc<Func<T, R>>> Y1Exp = f => util.ConvF<SFunc1<Func<T, R>>, YFunc<Func<T, R>>>
                (x => y => x(y)(x))(y => x => z => y(x(y)(x))(z))(f);
    
            public static readonly Expression<YFunc<Func<T, R>>> TuringExp = f => util.ConvF<SFunc<YFunc<Func<T, R>>>, YFunc<Func<T, R>>>
                (x => y => z => y(x(x)(y))(z))(x => y => z => y(x(x)(y))(z))(f);
        }
    
        public static class Recursive
        {
            public static Func<T, R> Make<T, R>(SFunc<T, R> f)
            {
                return x => f(f, x);
            }
        }
    }
    

    说明一下,以上代码包括了纯Lambda表达式里不动点组合子的3种形式,正式名称是Y,Y'和Turling,外加装配脑袋利用C#内建递归的一种,以及博主不用不动点实现递归的一种。由于处理各种形式的Action和Func极为不便,这里还提供了一些辅助函数让它们可以和Func的标准形式互相转换。基本的理论就是f(x,y)和g(x)(y)可以互相转换,以及在Action上调用DynamicInvoke可以返回一个object。本来,a();return null;可以达到同样效果,但它不能转换为Linq Expression Tree, 而我对于三种纯粹Lambda表达式都有提供其Linq Expression Tree形式。

    做各种不动点组合子时,最难的是推导其中涉及的类型。为此我推出了SelfApplicable(我用的名称是SFunc)的3种形式,一种用于2种不动点组合子(装配脑袋的那种),一种用于另一种组合子(它在返回类型上递归),还有一种就是博主的那种,仅用于博主的递归实现方法。

  69. earthengine
    112.213.212.*
    链接

    earthengine 2010-11-22 17:25:49

    如果我们规定所有出现的函数必须是一元函数,那么博主的Make要改写为顺序递交参数的形式。

    Func<T, R> Make<T, R>(SelfApplicable<T, R> v) { return x => v(v)(x); }
    

    但是x => v(v)(x)就是 v(v),所以可以简化成

    Func<T, R> Omega(SelfApplicable<T, R> v) { return v(v); }
    

    这个在lambda表达式里面就叫做ω组合子。 用它实现的fact形式如下:

    var fac = Omega<int, int>(f => x => x <= 1 ? 1 : x * f(f)(x - 1));
    

    或者,用纯粹的lambda表达式可以写成

    var fac = (v => v(v))(f => x => x <= 1 ? 1 : x * f(f)(x - 1));
    

    但这个无法编译,因为C#无法自动推断v => v(v)的类型。要解决这个问题,引入一个辅助函数,在我上一个回帖里面看上去无用,却在一元函数的世界里扮演重要角色的 util.ConvF, 它接受一个函数,返回一个它的代理,有相同的参数和返回值。这个东西就不用写出实现了吧。它在这里的作用,是当结合两个Lambda表达式(把一个作为参数传给另一个)的时候可以靠它显式指定第一个表达式的类型,从而避免使用强制。

    var fac = util.ConvF<SelfApplicable<int, int>, Func<int, int>> (v => v(v))(f => x => x <= 1 ? 1 : x * f(f)(x - 1));
    

    这看上去也不错。gcd怎么办?

    var gcd = util.ConvF<SelfApplicable<int, Func<int,int>>, Func<int, Func<int, int>>> 
    (v => v(v))(f => x => y == 0 ? x : f(f)(y)(x % y));
    

    总结一下,当采用ω组合子实现递归时,所要做的是将原来的按名字递归的程序提炼出一个新的参数f,然后在所有递归引用的地方,把原来函数的名字改成f(f)。

  70. earthengine
    112.213.212.*
    链接

    earthengine 2010-11-22 18:33:20

    如果进一步想要消除那个讨厌的f(f),直接使用

    Func<int, int> fac = (f => x => x <= 1 ? 1 : x * f(x - 1));
    

    就需要找一个别的东西代替ω组合子。为此我们观察上面的函数体,它接受一个函数f作为其参数。那么我们想一下,什么样的函数可以成为它的参数呢?它必须是一个Func<int, int>。此外,fac(f)也是一个Func<int, int>,且和f必须有相同的功能,不然的话,它就不是真正的递归了。fac(f) = f,用数学术语说,它就是f的不动点。楼主那个来自装配脑袋的Fix就可以用,但是我们可以有别的思路。我们写下这样的代码

    Func<T, R> fix<T, R>(Func<Func<T, R>, Func<T, R>> v)
    {
        Func<T, R> _fixedpoint = v(_fixedpoint);
        return _fixedpoint;
    }
    

    这样当然不能编译。但如果采用一开始解决未初始化变量问题的思路,这个问题也可以解决。

    Func<T, R> fix<T, R>(Func<Func<T, R>, Func<T, R>> v)
    {
        Func<T, R> _fixedpoint = null;
        _fixedpoint = v(_fixedpoint);
        return _fixedpoint;
    }
    

    不过还是不行,因为执行到赋值语句的时候, _fixedpoint是null,所以相当于提前传给了g函数一个null,这样后面递归的时候就会出错。解决方法是众所周知的“引入一个中间层“,

    Func<T, R> fix<T, R>(Func<Func<T, R>, Func<T, R>> v)
    {
        Func<T, R> _fixedpoint = null;
        _fixedpoint = x => v(_fixedpoint)(x);
        return _fixedpoint;
    }
    

    这下,对fixedpoint的引用被延迟到了fixedpoint被实际赋给了一个参数的时候,因此这时候它早已经有值了。 这个怪函数就这样子实现了和脑袋的Fix一样的功能。

    现在脑袋进一步转动,我们看到这个fix函数里面有递归,所以不能直接转换为lambda表达式。但是我们已经开发出了基于ω组合子的递归lambda表达式实现,所以我们把它套用到fix身上。这里发生递归的是一个叫fixedpoint的变量,这个变量的值是v(fixedpoint),所以我们可以首先写出函数体:

    Func<Func<T, R>, Func<T, R>> _fixedpointbody = f => v(f(f));
    

    还记得吗,对递归函数体的要求是递归点要用附加参数的自我调用代替,在这里f(f)就是递归点。但是这里没有v的位置,这个函数仅仅代表fix函数体里面对_fiedpoint的调用。现在我们把ω组合子作用于其上,

    Func<T, R> _fixedpoint = (f=>f(f))(f => x => v(f(f))(x));
    

    这里我们暂时忽略类型推断的难题。据此我们已经可以写出fix的纯lambda实现。

    Func<T, R> fix = v => (f=>f(f))(f => x => v(f(f))(x));
    

    这里的类型推断需要发生在lambda函数体内部,如果使用强制甚至ConvF都会破坏掉lambda表达式的完整性。为了让结果更漂亮,也为了演示lambda表达式和函数式编程的风格,我们再改变一下,把ω组合子作为参数传给fix函数体。

    Func<T, R> fix = (h => v => h(f => x => v(f(f))(x)))(f => f(f));
    

    最后,推断一下类型让它能编译:

    Func<T, R> fix = util.ConvF<SelfApplicable<T, R>, Func<Func<Func<T, R>, Func<T, R>>, Func<T, R>>>
        (h => v => h(f => x => v(f(f))(x)))(f => f(f));
    

    现在写fac会是这样子的:

    Func<int, int> fac =
        util.ConvF<SelfApplicable<int, int>, Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>>>
                (h => v => h(f => x => v(f(f))(x)))
                (f => f(f))
                (f => n => (n <= 1) ? 1 : n * f(n - 1));
    

    思考题:脑袋的那个版本的Fix能不能找到等价的lamba表达式?生成的lambda表达式是怎么样的?对应的ConvF类型指派如何确定?

  71. 数据库之家
    118.122.85.*
    链接

    数据库之家 2012-07-09 10:49:14

    老大, 问个不是问题的问题:您是怎么知道这些的?

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我