读书人
栏目▼

关于递归和Lambda用Fixed Point Com

发布时间： 2012-01-28 22:06:14 作者： rapoo

关于递归和Lambda，用Fixed Point Combinator实现
为了简化起见，我们用一个最简单的递归例子来展开讨论。
计算 sum(1 to n)，f(n) (n > 0，不考虑负数)可以表达为：
f = 1 when n = 1, f = n + f(n - 1) when n > 1。

一上来，很多人肯定想到这么写：

C# code
Func<int, int> f = x => { if (x == 1) return 1; else return x + f(x - 1); };
结果编译器报错，使用f前没有初始化。

cnblog的装配脑袋给出了最佳实践，Fixed Point Combinator，不动点组合子。老赵也引用了这一做法，但是没有给出解释。当然，数学好的朋友理解起来不难，但是大多数人，比如我，数学很菜。所以我想试着帮助老赵来解释下。

这一做法的本质是，将递归展开变成递推函数，然后计算。
假设 x = 1，那么 f(x) 被调用 1 次。我的表述可能不正规，姑且记作 f1(1) = f(1) = 1
假设 x = 2，那么 f(x) 被调用 2 次，求 f(2) 的函数也可以表述成 f2(2) = 2 + f1(1) = 2 + 1
假设 x = 3，那么 f(x) 被调用 3 次，求 f(3) 的函数也可以表述成 f3(3) = 3 + f2(2) = 3 + 2 + f1(1) = 3 + 2 + 1
所谓不动点，我的理解就是这里的f1 f2 f3 ...就是不动点。（我数学不好，这么理解是否可以请指正）

也就是说，对于任意 x = n，我们都可以找到一个等效的函数fn，比如说 f100 = 100 + 99 + 98 + ... + 1。

绕了一圈回来了，的确用递归算数字求和小题大做。但是这说明了递归可以被展开的事实。

然后我们想，既然 f(x) 可以用 fx(x) 来代替，那么我们可以这么做：给定一个x，我们不用f(x)，而是展开成fn来计算。
比如：
Func<int, int> GetFn(n)
{
if (n == 1) return x => 1 //注意，当 n = 1 的时候，fn(n) = f(n)，这就是说计算1+2+...+100的函数你拿来1+2+...+10肯定不对了。
if (n == 2) return x => 1 + 2;
if (x == 3) return x => 1 + 2 + 3;
...
}
调用 int sum = GetFn(n)(n);

你要说了，多么傻的办法，再说 n 也没有个头，你这个造到哪里去。

要是计算机自动能自动构造出一个求和的函数就好了。

重点来了。
我们从API调用者的角度看，我们需要这么一个函数：
输入一个原函数，自动生成一个可以计算n的展开函数（不动点函数）。

顺便说下，这种让计算机自动产生代码的编程方式叫做 meta programming（元编程）。

对于一个 Func<int, int>的原函数，它的自动生成不动点函数的调用可以这么写：
C# code
static Func<T, TReturn> FixedPointCombinator<T, TReturn>(Func<Func<T, TReturn>, Func<T, TReturn>> func){}

怎么解决？
没错，就是这个公式：
fix(F)(n) = F(fix(F))(n) 参考：http://zh.wikipedia.org/wiki/%E4%B8%8D%E5%8A%A8%E7%82%B9%E7%BB%84%E5%90%88%E5%AD%90

C# code
static Func<T, TReturn> FixedPointCombinator<T, TReturn>(Func<Func<T, TReturn>, Func<T, TReturn>> func){    return x => func(FixedPointCombinator(func))(x);}

函数有了，我们调用下：
C# code
static void Main(string[] args){    var func = FixedPointCombinator<int, int>(f => x => { if (x == 1) return 1; else return x + f(x - 1); });    Console.WriteLine(func(100));            }


运算结果，5050，正确。

完整的程序：
C# code
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace ConsoleApplication1{    class Program    {        static Func<T, TReturn> FixedPointCombinator<T, TReturn>(Func<Func<T, TReturn>, Func<T, TReturn>> func)        {            return x => func(FixedPointCombinator(func))(x);        }        static void Main(string[] args)        {            var func = FixedPointCombinator<int, int>(f => x => { if (x == 1) return 1; else return x + f(x - 1); });            Console.WriteLine(func(100));                    }    }}


再想一想。

一般的递归就是直接调用递归函数，自己调用自己求解。
Fixed Point Combinator，将递归函数作为参数（模板），内部用递归方法构造不动点算子（展开递归函数），最后将对递归的调用转化为对不动点函数的调用，求解。

好了，我写完了，不知道大家理解了没有。其实很简单的。

[解决办法]
我的理解就是一方法套一匿名代理, 很有技巧。。。
------解决方案--------------------


Y Combinator
c#的实现


[解决办法]

探讨

Y Combinator
c#的实现

[解决办法]
恩。很早之前看过Y算子。不过有简化的嵌套递归写法。
C# code
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace ConsoleApplication1{    class Program    {        static void Main(string[] args)        {            var func = null;//先声明为null就可以嵌套，编译通过了            func = f => x => (x == 1)?1:x + func(x - 1); };            Console.WriteLine(func(100));                    }    }}
[解决办法]
擦。多了

C# code
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace ConsoleApplication1{    class Program    {        static void Main(string[] args)        {            var func = null;//先声明为null就可以嵌套，编译通过了            func = x => (x == 1)?1:x + func(x - 1); };            Console.WriteLine(func(100));                    }    }}
[解决办法]
func = x => (x == 1) ? 1 : x + func(x - 1);

er...
没编译器。再修改一次。
[解决办法]
C# code
//以前看到的using System;using System.Collections.Generic;public class Test{delegate T SelfApplicable<T>(SelfApplicable<T> self);private static void Main(){    SelfApplicable<Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>>>    Y = y => f => x => f(y(y)(f))(x);    Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>>    Fix = Y(Y);    Func<Func<int, int>, Func<int, int>>    F = fac => x => x == 0 ? 1 : x * fac(x - 1);    Func<int, int> factorial = Fix(F);    System.Console.WriteLine(factorial(4).ToString());}}
[解决办法]
探讨
func = x => (x == 1) ? 1 : x + func(x - 1);

er...
没编译器。再修改一次。

[解决办法]
探讨

引用:
Y Combinator
c#的实现

对，我之前就看到了装配脑袋的文章（我文中提到他的）。

我现在的想法就是有时间把计算机科学和数学从头再学一遍。我基础太差了。

[解决办法]
cnblog的装配脑袋

ps: 脑袋早期是混CSDN的，ID ：Ninputer

[解决办法]
探讨

cnblog的装配脑袋

ps: 脑袋早期是混CSDN的，ID ：Ninputer

[解决办法]
再说两句题外话，刚看了cj和郑晖老师的Q&A.

回复中三句标黑的句子，两句是真传。(另外那句也是可以理解的 :) )

对于Programer  


英语要比想象中更为重要

数学很重要

第二句没有全部标红，是因为Programer 所从事的内容是不一样的，数学对他们的重要性也是不一样的

但最基本的是数学带动的思维方式，可以帮助我们学会用归纳、抽象来应对变化，这个是核心。

虽然郑晖老师略感抱歉的表示没说什么具体的建议，但实则已将准则写了出来。

虽说 “真传一页纸，假传万卷书”

但没有万卷书做为基础，那一页纸的真传是领悟不了的。

这个道理，相信你深深懂得，我也只是给初学者铺路而已。


打雷啦！！ 下雨收衣服啊！！！
[解决办法]
实在看不下去帖子里的内容。
过来支持两下。
其实我觉得数学和英语都很重要。
不过我认为还有一个更重要的在于坚持。
[解决办法]
呵呵，数学没看出来，到是在语文的前后语句的逻辑上，感觉有点奇怪，疑惑的地方是： 
 
引用您的原话：
但是大多数人，比如我，数学很菜。所以我想试着帮助老赵来解释下。
为什么是这样的逻辑呢？数学越不好=》越应该去解释这种问题？呵呵，可能是我文科不好，没能理解您深层次上的逻辑=》数学越不好=》越应该去解释技术问题，但是就我个人看来感觉罗嗦上有点别扭！但是也许这么说也是没错的！

不好意思，如果是我指正错误，就当我没说！

[解决办法]
探讨

C# code

  Func<int, int> func = null;//先声明为null就可以嵌套，编译通过了
  func = x => (x == 1) ? 1 : x + func(x - 1);
  ……

[解决办法]

[解决办法]
顶一个先。。
正在安装VS2010，以前也自学过一点Lamada，对此也非常感兴趣，无奈公司装的VS2005，这两天闲下来了看下递归和LAMADA，一会儿编译下9 楼 claymore1114 同学的代码。。
学习中。。。
此贴收藏了。。
[解决办法]
太蛋疼了，包括MSDN推荐的方法都很蛋疼，看看我的blog吧，看看什么才是lambda递归，其实非常非常非常的简单，几乎不需要任何冗余语句。要解决直接编译会编译错误的解决方案，就是先定义一个func f=null

  更简洁的使用lambda递归
http://blog.csdn.net/aimeast/archive/2010/03/12/5375239.aspx
C# code
static void Main(string[] args)  {      //这里要注意！！      //必须要先赋值后才可以进行递归定义。否则会编译出错      Func<int, int> fac = null;      fac = (x => x == 0 ? 1 : x * fac(x - 1));      for (int i = 0; i < 10; i++)      {          Console.WriteLine("{0} : {1}", i, fac(i));      }  }
[解决办法]
既然这样你不如去学F#，F#解决这类问题更优雅...前两年研究了几天，后来没心思看了...
[解决办法]
这是产生式编程得一个非常特别得例子，特别之处在于，他是最普通，最本质得，所以，是非常特别得函数，
而元编程含义大于产生式编程，产生式编程是人类，元编程是人类社会！！！！！！！！！！！！
[解决办法]
同意
C# code
Func<int, int> f = null;f = x => x == 1 ? 1 : x + f(x - 1);
[解决办法]
所有得递归问题都可以转换成递推得推论是，任何一个功能，能被动态产生得递推实现，而这个动态产生式可以是一个字符串，而字符串，有可以被任意替换，这就是说任何一个功能可以被动态得替换成另一个功能！！！！！！！！！！！！！！！！！！！！！！！！！
[解决办法]
http://hi.baidu.com/feixue/blog/item/e809baa1bd3c549c47106429.html

在参考了本贴及其它资料后的总结：

本文主要总结了一些资料中对Y组合子的推导,最后参考其中一份C#代码,并给出了C++0x中的实现.
个人认为,直真正实现Y组合子的是文中出现的第一份C#代码,其它的实现借助了对函数递归的支持.

1.直接递归不行,因为在定义中出现了自己;
2.通过参数的形式把递归的部分传进去(记为F);
3.假设目标为f,于是F(f) = f,问题转换为求F的不动点;
4.知道高阶Fix满足性质:Fix(F) = F(Fix(F)),现在目标是找到这样的Fix;
5.两个推导思路
5.1
 构造一个式子,使之满足F(f) = f;
 如果具有A(b) = F(b(b))的形式的函数则w(A) = F(w(A));
 如果构造一个函数以F为参数，返回w(A)则就是Y组合子;
 得到Y = g => (b=>g(b(b))) (b=>g(b(b))).
5.2
 构造一个组合子Y,接受一个参数y表示本身,还有一个参数f表示一个高阶函数,使得能
 返回f的不动点;
 于是Y有形式Y = y => f => ???;
 根据定义???部分就是:y(y)(f);
 但是现在的结果平凡的,只是没有意义地展开,注意到不动点性质,于是???可以是
    f(y(y)(f));
 但是上面得到的结果在惰性计算的情况下才可行,于是要构造一个传值的:
    Y = y => f => x => f(y(y)(f))(x);
 于是最后Y(Y)为所求.
6.根据5.2在C#中的实现.
 首先Y的类型的参数类型和Y一样于是:
 delegate T SelfApplicable<T>(SelfApplicable<T> self)
 这样就构造了一个委托,其参数类型是自身,返回类型待定.
 注意到5.2中的结果:
 f => x => f(y(y)(f))(x);是返回的表达式,这个表达式的类型是
 Func<int, int>
 f的类型可以2推导出来.
 fac => x => x == 0 ? 1 : x * fac(x - 1);
 可以看到参数类型是fac : Func<int, int>
 返回类型是: Func<int, int>
 于是最后的T : Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>>
 得到如下C#代码:
C# code
using System;using System.Collections.Generic;public class Test{delegate T SelfApplicable<T>(SelfApplicable<T> self);private static void Main(){    SelfApplicable<Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>>>    Y = y => f => x => f(y(y)(f))(x);    Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>>    Fix = Y(Y);    Func<Func<int, int>, Func<int, int>>    F = fac => x => x == 0 ? 1 : x * fac(x - 1);    Func<int, int> factorial = Fix(F);    System.Console.WriteLine(factorial(4).ToString());}} 
 
[解决办法]
装配脑袋有些纠结于vb.net，所以对以前版本的vb.net对lamda只支持单行而不支持c#那种多行（例如
C# code
Func<int, int> f = x =>{    var result = 0;begin:    result += x;    if (x == 1)        return result;    else    {        x--;        goto begin;    }};
[解决办法]
探讨
引用:
http://hi.baidu.com/feixue/blog/item/e809baa1bd3c549c47106429.html

在参考了本贴及其它资料后的总结：

本文主要总结了一些资料中对Y组合子的推导,最后参考其中一份C#代码,并给出了C++0x中的实现.
个人认为,直真正实现Y组合子的是文中出现的第一份C#代码,其它的实现借助……

[解决办法]
不允许代码
C# code
Func<int, int> f = x => { if (x == 1) return 1; else return x + f(x - 1); };
[解决办法]
既然只是编译器造成的问题（而不是运行时的问题），这就非常好解决，而不必使用很复杂的理论（我相信所有人都喜欢简单的方法办大事，而不喜欢复杂的方法办小事）。在一个需要lamda表达式得地方，如果你觉得不好写，那么就另外写一个实名的函数，然后在这个需要lamda表达式的地方调用它（或者表达式其中一部分调用它）这就行了。除非我们遇到了不允许编写自定义函数的开发平台，才需要去研究更复杂的理论。
[解决办法]
探讨
如果我没有记错，C# 3的Lambda表达式也必须写在一行？还是不允许没有返回值的Lambda表达式

[解决办法]
lambda执行效率上还是欠佳，内置函数比不过设计的算法。不知道大家有没有注意
[解决办法]
C/C++ code
//c++中，虽然在定义语句中并没有完全定义，但是在里面这个标识符已经可以用了//以前论坛中有人提到过的一个问题就是int x = x;何解function<int (int)> fac = [&](int x)->int{return x == 0 ? 1 : x * fac(x-1);};
读书人网 >C#

热点推荐

触屏版 | 电脑版

读书人网 m.reader8.net