Skip to content

Instantly share code, notes, and snippets.

@redraiment
Last active December 23, 2020 07:44
Show Gist options
  • Save redraiment/6445345 to your computer and use it in GitHub Desktop.
Save redraiment/6445345 to your computer and use it in GitHub Desktop.
Y Combinator (Fixed-point 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. 三元表达式的使用方法。
等诸多语法特性
(defn y-combinator [f]
(#(% %) (fn [x] (f #(apply (x x) %&)))))
((y-combinator
(fn [fab]
#(if (zero? %) 1 (* % (fab (dec %))))))
10)
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);
(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)
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))
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);
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);
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)
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]
(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
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));
}
}
@gaoryrt
Copy link

gaoryrt commented Mar 29, 2019

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)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment