10种编程语言实现Y组合子版的递归阶乘函数，递归阶乘,Y组合子是Lambda演

10种编程语言实现Y组合子版的递归阶乘函数，递归阶乘,Y组合子是Lambda演

Y组合子是Lambda演算的一部分，也是函数式编程的理论基础。

它是一种方法/技巧，在没有赋值语句的前提下定义递归的匿名函数。

即仅仅通过Lambda表达式这个最基本的“原子”实现循环/迭代。

颇有道生一、一生二、二生三、三生万物的感觉。

虽然Y组合子在理论上很优美，但在实际开发中并不会真的用到。

想要了解Y组合子是什么，请参见维基百科：http://en.wikipedia.org/wiki/Fixed-point_combinator#Y_combinator

下面用10种不同的编程语言实现了Y组合子版的递归阶乘函数。

分别展示了在这10种语言

如何定义、返回、调用匿名函数；

如何定义参数数目不定的函数；

如何将数组里的元素平坦开来传递给函数；

三元表达式的使用方法。

等诸多语法特性

//Clojure版  (defn y-combinator [f]  (#(% %) (fn [x] (f #(apply (x x) %&)))))((y-combinator  (fn [fab]    #(if (zero? %) 1 (* % (fab (dec %)))))) 10)//Scheme版(define (y-combinator f)  ((lambda (u)     (u u))   (lambda (x)     (f (lambda args          (apply (x x) args))))))((y-combinator  (lambda (fab)    (lambda (n)      (if (zero? n)          1          (* n (fab (- n 1))))))) 10) ; => 3628800//Common Lisp版(defun y-combinator (f)  ((lambda (u)     (funcall u u))   (lambda (x)     (funcall f (lambda (&rest args)                  (apply (funcall x x) args))))))(funcall (y-combinator          (lambda (fab)            (lambda (n)              (if (zerop n)                1                (* n (funcall fab (1- n)))))))         10)//JavaScript版 var y_combinator = function(fn) {    return (function(u) {        return u(u);    })(function(x) {        return fn(function() {            return x(x).apply(null, arguments);        });    });};y_combinator(function(fab) {    return function(n) {        return n <= 1? 1: n * fab(n - 1);    };})(10);//PHP版function y_combinator($f) {    return call_user_func(function($u) {        return $u($u);    }, function($x) use ($f) {        return $f(function() use ($x) {            return call_user_func_array($x($x), func_get_args());        });    });}echo call_user_func(y_combinator(function($fab) {    return function($n) use ($fab) {        return ($n < 2)? 1: ($n * $fab($n-1));    };}), 10);//Perl版sub y_combinator {    my $f = shift;    sub { $_[0]->($_[0]); }->(sub {        my $x = shift;        $f->(sub { $x->($x)->(@_); });    });}print y_combinator(sub {    my $fab = shift;    sub { $_[0] < 2? 1: $_[0] * $fab->($_[0] - 1); };})->(10);//Python版  def y_combinator(f):    return (lambda u: u(u))(lambda x: f(lambda *args: x(x)(*args)))y_combinator(lambda fab: lambda n: 1 if n < 2 else n * fab(n-1))(10)//Ruby版def y_combinator(&f)  lambda {|&u| u[&u]}.call do |&x|    f[&lambda {|*a| x[&x][*a]}]  endendy_combinator do |&fab|  lambda {|n| n.zero? ? 1: n*fab[n-1]}end[10]//Lua版function y_combinator(f)    return (function(u)        return u(u)    end)(function(x)        return f(function(...)            return x(x)(unpack(arg))        end)    end)endprint(y_combinator(function(fab)    return function(n)        return n < 2 and 1 or n * fab(n-1)    endend)(10))//Java版package me.zzp.fn;public class YCombinator {    interface Lambda<E> {        public E call(Object... args);    }    public static Lambda<Lambda> yCombinator(final Lambda<Lambda> f) {        return new Lambda<Lambda>() {            @Override            public Lambda call(Object... args) {                final Lambda<Lambda> u = (Lambda<Lambda>) args[0];                return u.call(u);            }        }.call(new Lambda<Lambda>() {            @Override            public Lambda call(Object... args) {                final Lambda<Lambda> x = (Lambda<Lambda>) args[0];                return f.call(new Lambda<Object>() {                    @Override                    public Object call(Object... args) {                        return x.call(x).call(args);                    }                });            }        });    }    public static void main(String[] args) {        Lambda<Lambda> y = yCombinator(new Lambda<Lambda>() {            @Override            public Lambda call(Object... args) {                final Lambda<Integer> fab = (Lambda<Integer>) args[0];                return new Lambda<Integer>() {                    @Override                    public Integer call(Object... args) {                        Integer n = Integer.parseInt(args[0].toString());                        if (n < 2) {                            return Integer.valueOf(1);                        } else {                            return n * fab.call(n - 1);                        }                    }                };            }        });        System.out.println(y.call(10));    }}//该片段来自于http://byrx.net