Instantly share code, notes, and snippets.

# Jason-Chen-2017/Y Combinator 简介

Forked from redraiment/Y Combinator 简介
Created July 9, 2017 08:42
Show Gist options
• Save Jason-Chen-2017/88e13b63fa5b7c612fddf999739964b0 to your computer and use it in GitHub Desktop.
Y Combinator (Fixed-point Combinator) 不动点组合子
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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. 三元表达式的使用方法。 等诸多语法特性
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (defn y-combinator [f] (#(% %) (fn [x] (f #(apply (x x) %&))))) ((y-combinator (fn [fab] #(if (zero? %) 1 (* % (fab (dec %)))))) 10)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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);
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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);
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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);
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 package me.zzp.fn; public class YCombinator { interface Lambda { public E call(Object... args); } public static Lambda yCombinator(final Lambda f) { return new Lambda() { @Override public Lambda call(Object... args) { final Lambda u = (Lambda) args[0]; return u.call(u); } }.call(new Lambda() { @Override public Lambda call(Object... args) { final Lambda x = (Lambda) args[0]; return f.call(new Lambda