关于递归和Lambda，用Fixed Point Combinator实现

Question

本帖最后由 caozhy 于 2011-05-05 06:03:34 编辑

Answer 1

Y Combinator
c#的实现

Answer 2

恩。很早之前看过Y算子。不过有简化的嵌套递归写法。
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));            
        }
    }
}

Answer 3

擦。多了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));            
        }
    }
}

Answer 4

func = x => (x == 1) ? 1 : x + func(x - 1);er...
没编译器。再修改一次。

Answer 5

//以前看到的
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());
}
}

Answer 6

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

Answer 7

郑晖老师有过这方面的回答（关于学数学）http://blog.zhenghui.org/2010/06/03/advice-on-programmer/
装配脑袋童鞋也不是一般的好功底，我曾经也有和你一样的打算，因为上面博文的提问人其实就是我。总体来看，你的基本功在我之上很多了。所以我觉得更多的可以考虑从算法角度来进行一些充实就OK了
JeffreyZhao的解决方案很容易理解，也可以很好的吸收，如果没有特殊需要，我觉得就他的解决方案就可以接受了。至于Y Combinator，Pongba的博文我觉得从数学的角度考虑的更多些，更有意思一点~

Answer 8

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

Answer 9

人家最后一次出现在csdn可能是06年的事儿了吧
很多人已经不在了。走了穿红的来了挂绿的。
不讨论这些了，水分较大逍遥之前似乎还拿类似问题作为对lambda掌握能力的依据吧。
pongba的博文我第一次看的时候云里雾里，因此我连续3年每年都看一遍。但是依然不是很清晰

Answer 10

再说两句题外话，刚看了cj和郑晖老师的Q&A.回复中三句标黑的句子，两句是真传。(另外那句也是可以理解的 :) )对于Programer 
英语要比想象中更为重要

数学很重要第二句没有全部标红，是因为Programer 所从事的内容是不一样的，数学对他们的重要性也是不一样的但最基本的是数学带动的思维方式，可以帮助我们学会用归纳、抽象来应对变化，这个是核心。虽然郑晖老师略感抱歉的表示没说什么具体的建议，但实则已将准则写了出来。虽说 “真传一页纸，假传万卷书”但没有万卷书做为基础，那一页纸的真传是领悟不了的。这个道理，相信你深深懂得，我也只是给初学者铺路而已。
打雷啦！！ 下雨收衣服啊！！！

Answer 11

这个表示同意，如果是var的话，编译器应该会迷惑的。
看来很多童鞋的研究很深入啊，不像我停留在工具使用层面上，檫，檫。

Answer 12

顶一个先。。
正在安装VS2010，以前也自学过一点Lamada，对此也非常感兴趣，无奈公司装的VS2005，这两天闲下来了看下递归和LAMADA，一会儿编译下9 楼 claymore1114 同学的代码。。
学习中
此贴收藏了。。

Answer 13

太蛋疼了，包括MSDN推荐的方法都很蛋疼，看看我的blog吧，看看什么才是lambda递归，其实非常非常非常的简单，几乎不需要任何冗余语句。要解决直接编译会编译错误的解决方案，就是先定义一个func f=null 更简洁的使用lambda递归
http://blog.csdn.net/aimeast/archive/2010/03/12/5375239.aspx
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));  
    }  
}  

Answer 14

同意Func<int, int> f = null;
f = x => x == 1 ? 1 : x + f(x - 1);
的写法。
既然要另外定义一个臃肿的方法，那还不如直截了当地把f定义为方法int f(int i)
{
    return i == 1 ? 1 : i + h(i - 1);
}

Answer 15

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#代码:
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());
}
}
  利用函数本身的递归的实现,更具有实用价值:
using System;
using System.Collections.Generic;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));            
        }
    }
}
在C++0x中改写上述代码(gcc version 4.5.2 (tdm-1),Microsoft Visual Studio 2010 10.0.30319.1 RTMRel):
#include <iostream>
#include <functional>
using namespace std;typedef function<int (int)> fp;
template<typename T>
T fix(function<T (T)> func)
{
 return [=](int x)->int{return (func(fix(func)))(x);};
}int main()
{
 function<fp (fp)> F = [=](fp fac)->fp{return [=](int x)->int{return x==0?1:x*fac(x-1);};};
 fp factorial = fix(F);
 cout << factorial(10) << endl;
 return 0;
}7.说明:
1-4基本上在所有的参考资料里都有提.
5.1主要参考[4].
6中的文字部分主要参考[2],代码来源也是[2],第二份代码在[5]中被引用(有修改).
根据[2],5.2中提到的Y组合子和其它的不同,但是本质一致.8.参考资料:
[1] http://mindhacks.cn/2006/10/15/cantor-godel-turing-an-eternal-golden-diagonal/
[2] http://blogs.msdn.com/b/madst/archive/2007/05/11/recursive-lambda-expressions.aspx
[3] http://www.cnblogs.com/Ivony/archive/2009/09/03/1559288.html
[4] http://www.cnblogs.com/Ivony/archive/2009/09/03/1559349.html
[5] http://topic.csdn.net/u/20110504/15/B3F85411-A630-44F8-AAE6-A1EC0102158A.html

Answer 16

能得到sp1234的点拨，实在是一件荣幸的事情。貌似sp1234最近来的少。还要感谢其他给予指导的每一位大牛。

Answer 17

装配脑袋有些纠结于vb.net，所以对以前版本的vb.net对lamda只支持单行而不支持c#那种多行（例如Func<int, int> f = x =>
{
    var result = 0;
begin:
    result += x;
    if (x == 1)
        return result;
    else
    {
        x--;
        goto begin;
    }
};
）的定义方法一直耿耿于怀。其实即使是在早期只支持单行语句的vb.net中，也可以在不方便写匿名函数的时候直接转而使用实名的函数来方到lamda表达式中。实际上这是编译器不够强的问题（早期的vb.net编译器设计者对lamda仅仅支持一点点）。

Answer 18

不允许代码Func<int, int> f = x => { if (x == 1) return 1; else return x + f(x - 1); };在编译时通过，我认为这纯粹是编译器设计问题，我不认为说“因为在定义中出现了自己”这是一个好的借口，因为这样的代码并没有歧义，而是一目了然的。所以我认为编译器迟早会支持这种代码通过（同时也完全兼容于低版本编译器支持下的代码）。

Answer 19

如果我没有记错，C# 3的Lambda表达式也必须写在一行？还是不允许没有返回值的Lambda表达式？

Answer 20

其实我想侧重演示的是 meta programming。但是我的确没有注意到先行定义直接就可以实现Lambda的递归了。

Answer 21

既然只是编译器造成的问题（而不是运行时的问题），这就非常好解决，而不必使用很复杂的理论（我相信所有人都喜欢简单的方法办大事，而不喜欢复杂的方法办小事）。在一个需要lamda表达式得地方，如果你觉得不好写，那么就另外写一个实名的函数，然后在这个需要lamda表达式的地方调用它（或者表达式其中一部分调用它）这就行了。除非我们遇到了不允许编写自定义函数的开发平台，才需要去研究更复杂的理论。

Answer 22

不是这个意思。“装配的脑袋”研究的是早期的vb.net，而不是c#。所以在c#中早几年就实现了的功能，在它看来vb.net代码中无法简单地实现，而他又拼命地想“绝对不用传统的方法（例如自己定义一个独立的f函数）来实现”，他拼命地想仅仅用vb.net中新功能来实现。

Answer 23

lambda执行效率上还是欠佳，内置函数比不过设计的算法。不知道大家有没有注意

Answer 24

//c++中，虽然在定义语句中并没有完全定义，但是在里面这个标识符已经可以用了
//以前论坛中有人提到过的一个问题就是int x = x;何解
function<int (int)> fac = [&](int x)->int{return x == 0 ? 1 : x * fac(x-1);};