Y Combinator (Fixed-point Combinator) 不动点组合子

Y Combinator 简介

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

它是一种方法/技巧，在没有赋值语句的前提下定义递归的匿名函数。
即仅仅通过Lambda表达式这个最基本的“原子”实现循环/迭代。
颇有道生一、一生二、二生三、三生万物的感觉。

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

想要了解Y组合子是什么，请参见维基百科：http://en.wikipedia.org/wiki/Fixed-point_combinator#Y_combinator
或者知乎上的回答：http://www.zhihu.com/question/20115649

下面用10种不同的编程语言实现了Y组合子版的递归阶乘函数。
分别展示了在这10种语言
1. 如何定义、返回、调用匿名函数；
2. 如何定义参数数目不定的函数；
3. 如何将数组里的元素平坦开来传递给函数；
4. 三元表达式的使用方法。
等诸多语法特性

y-combinator.clj

(defn y-combinator [f]
  (#(% %) (fn [x] (f #(apply (x x) %&)))))

((y-combinator
  (fn [fab]
    #(if (zero? %) 1 (* % (fab (dec %))))))
 10)

y-combinator.js

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);

y-combinator.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)

y-combinator.lua

function y_combinator(f)
    return (function(u)
        return u(u)
    end)(function(x)
        return f(function(...)
            return x(x)(unpack(arg))
        end)
    end)
end

print(y_combinator(function(fab)
    return function(n)
        return n < 2 and 1 or n * fab(n-1)
    end
end)(10))

y-combinator.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);

y-combinator.pl

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);

y-combinator.py

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)

y-combinator.rb

def y_combinator(&f)
  lambda {|&u| u[&u]}.call do |&x|
    f[&lambda {|*a| x[&x][*a]}]
  end
end

y_combinator do |&fab|
  lambda {|n| n.zero? ? 1: n*fab[n-1]}
end[10]

y-combinator.scm

(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

YCombinator.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));
    }
}

const y_combinator = f => (x => f(x(x)))(x => f((...v) => x(x)(...v)))

y_combinator(fab => n => n <= 1 ? 1 : n * fab(n - 1))(10)