谈lambda表达式中递归的使用

前几天笔试了网易的python,考了一道题,用lambda表达式写出求阶乘函数。当时python学了两个月不到,怎么可能会这么高深的学院派东东(姑且这么认为了,据说和lisp有关的东西地球人碰不得=。=)。
看可计算太无聊发现一个研究图灵机的链接康托尔、哥德尔、图灵——永恒的金色对角线,意外的是里面用很酷的方式帮助我理解了lambda表达式,感谢作者。之后我又去查了其他资料,感觉牛X的工具就是不一样。(这永远不能掩盖可计算理论是一门无聊的课这个事实)
—–
【语法基于python】
wiki写的历史
lambda calculus(λ演算)历史上它和可计算理论有很大关系,对Lisp/ML/Haskell等函数式编程语言有巨大的影响。
BNF语法
expr ::= identifier
expr ::= lambda identifier-list. expr
expr ::= (expr expr)
匿名函数
f(x)=x+2 –> lambda x: x+2
f(x, y)=x+y –> lambda x,y: x+y
匿名调用
(lambda x: x+3)(2) #output 5
(lambda x, y: x+y)(2, 3) #output 5
起个名再调用
F=lambda x, y: x+y
F(3, 4) #output 7
Alpha变换
lambda x, y: x+y –> lambda a, b: a+b
Beta变换
(lambda x, y:x+y)(2,3) –> 2+3
【核武器】递归
阶乘函数

def f(n):
    return n==0 and 1 or n*f(n-1)

–>

f = lambda self, n: n==0 and 1 or n*self(self, n-1)   #三处self特别重要
f(f, 5)   #output 120,第一个参数就是该函数自己~

我们可以很容易的将递归函数转换成lambda表达式。
【山寨武器】恼人的self
有人看了我上面的公式,觉得很多此一举,那个self完全可以不用嘛,而且使用f(f,5)实在是太难看了,有辱python这种牛X的语言,然后山寨武器出山!

f=lambda n: n==0 and 1 or n*f(n-1)
f(5)  #output 120

很简洁,完全切合了DRY原则(Don’t repeat yourself!)
不过就算它构造的再好,它永远是山寨武器,因为他不掌握核心技术!(f在lambda表达式的外面)
下面破招

f=lambda n: n==0 and 1 or n*f(n-1)
f(5)  #output 120
f2=f
f2(5)   #output 120, perfect
f=lambda x:x+1
f2(5)   #output 25 !!!  ERROR!!!

f2输出的结果是错的,为什么是25呢,仔细分析很容易就清楚了。
f后来引用的对象是lambda x:x+1,此时f(x)其实就是x+1
回到最开始的求阶乘lambda函数,它现在其实是lambda n: n==0 and 1 or n*((n-1)+1)
看出来了,lambda表达式现在的返回值等价于return n==0 and 1 or n^2
当然f2(5)就返回25咯~(事实上在很多其他语言中这样的定义是会报错的)
【拯救世界】–不动点
直接来一段代码

funA=lambda x: lambda y: y(lambda: x(x)(y))
funB=funA(funA)
f0=lambda self: lambda n: n==0 and 1 or n*self()(n-1)
f=funB(f0)
f(5)  #output 120

在这里通过一层包装,利用不动点的特性,我们直接用f(n)就可以了
文首链接的文章在不动点那里讲的太好了,我这里就不重复了,上面的python代码实现了那篇文章中的分析,结合起来看更容易弄懂。

至此结束
—–
我后悔没去听CS383了…(注:CS383是交大计算机系本科非常奇葩的一门课,全名叫“程序设计语言”,据传其中讨论了超过8种神奇的小众编程语言的思想与区别,特别是函数式编程,因考试和大作业极其坑爹曾在饮水思源BBS的CS板引发大范围讨论or吐槽)

Tags : ,

5 thoughts on “谈lambda表达式中递归的使用”

  1. 学习了, 原来lambda有一个self来指向自己……
    383讲的太理论( 以前的小笔记,当然帮助还是很大的),这学期给研究生开的课据说大作业就是做个lambda calculus的编译器。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Click the right image To submit your comment: