Y combinator in Python

在lambda系统中实现递归,需要借用Y组合算子(combinator)。下面是Python中的一个实作。

Y = lambda F: (lambda f: F(lambda x: f(f)(x))) (lambda f: F(lambda x: f(f)(x)))
F = lambda f: (lambda x: 1 if x==0 else x*f(x-1))

fact = Y(F)
print fact(10)

感觉这个Y combinator实在是令人头晕目眩,不知所以。具体的推导过程和相关理论,请参见刘未鹏先生的宏文,以及负暄琐话相关的blog(12)。读了几遍,仍然只是朦朦胧胧地明白了一点点,特别是后面的对角线,再读、再读... ...

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

To submit your comment, click the image below where it asks you to...
Clickcha - The One-Click Captcha