各语言Y组合子大比拼

最近有点无聊，突然想试试在各种语言里面实现Y组合子。不过写完之后，没想到结果完全出乎我的意料。嘛，让我们来看看不同语言里的Y组合子。

首先祭上Y组合子的定义：

Y = \lambda f. (\lambda x. f(x \, x)) \, (\lambda x. f(x \, x))

Python魔法

和众多流行的弱类型语言一样，Python支持lambda表达式但不支持延迟求解和柯里化，所以Python的写法应该也是比较有代表性的。

Y = lambda f: (lambda x: f(x(x)))((lambda x: f(lambda *args: x(x)(*args))))

可以看到，虽然有lambda加持，然而由于lambda这个单词真的好长，所以整个式子就变成了这样。另外，由于递归函数实际参数是传至右式的，所以左式并不需要传args。

JavaScript魔法

大部分如lua、php和Python并没有太大的区别。不过，时至ES6，js已经有了自己的lambda表达式——箭头函数。

Y = f => (x => f(x(x))) ((x => f(...a => x(x)(...a))))

由于无法脱离“函数调用要加括号”的苦海，于是纵使有简单的lambda写法，JS里成山的括号依旧令人无法直视。

CoffeeScript黑魔法

熟悉我的人一定知道，我个人是cs的脑残粉。cs的简洁与灵活和js（尤其是es5）真是天壤之别，函数调用可以省略括号也提供了极大的便利。

Y = (f) -> ((g) -> f (g g)) ((g) -> f (...x) -> (g g) ...x)

除了不支持柯里化导致不可避免的需要x，其余可以说是很完美了。

Haskell

那支持柯里化的语言是不是就无敌了？少年，天真了。

import Unsafe.Coerce
 
y :: (a -> a) -> a
y = \f -> (\x -> f (unsafeCoerce x x)) (\x -> f (unsafeCoerce x x))

由于Haskell有严格的类型检查，于是Y组合子这种“无限递归类型”的函数是无法通过类型检查的。不过，难道就没有不通过unsafeCoerce的方法嘛？想了一晚上，脑阔疼。不过作为SOO（StackOverflow Oriented）程序员我还是成功的找到了答案（原答案地址： https://stackoverflow.com/a/5885270 ）。

newtype Mu a = Mu (Mu a -> a)
y f = (\h -> h $ Mu h) (\x -> f . (\(Mu g) -> g) x $ x)

让我们来分析下这段代码。首先先用β归约：

y f = (\x -> f . (\(Mu g) -> g) x $ x) $ Mu (\x -> f . (\(Mu g) -> g) x $ x)

再次β归约：

y f = f . (\(Mu g) -> g) Mu (\x -> f . (\(Mu g) -> g) x $ x) $ Mu (\x -> f . (\(Mu g) -> g) x $ x))
    = f . (\x -> f . (\(Mu g) -> g) x $ x) $ Mu (\x -> f . (\(Mu g) -> g) x $ x))
    = f . y f

可以看出，这和Y组合子是等价的。而引入的Mu也同样起到了防止递归类型检查的效果。

Lisp（Scheme）

Haskell那边栽跟头主要是因为类型检查，那Lisp呢？（ 出处 ）

(define (Y f) (lambda (f)
      ((lambda (x)
         (f (lambda (arg) ((x x) arg))))
       (lambda (x)
         (f (lambda (arg) ((x x) arg)))))))

Scheme还是很纯粹很好看的。

Java作为一个有类型检查，lambda是语法糖的语言，想写Y组合子必然是痛苦的。我从 Gists 上找了一个：

package test;
 
import java.math.BigInteger;
import java.util.function.Function;
 
public class YCombinatorFactorial<T> {
    private interface Improver<T> {
        Function<T,T> apply( Improver<T> f ) ;
    }
 
    private Function<T,T> Y( final Function<Function<T,T>,Function<T,T>> r ) {
        return ((Improver<T>)f -> f.apply( f )).apply( f -> r.apply( x -> f.apply( f ).apply( x ) ) ) ;
    }
 
    public static void main( String[] args ) {
        YCombinatorFactorial<BigInteger> yf = new YCombinatorFactorial<BigInteger>() ;
        BigInteger result = yf.Y(
                f -> n -> n.equals( BigInteger.ZERO ) ?
                        BigInteger.ONE :
                        n.multiply( f.apply(n.subtract( BigInteger.ONE ) ) ) ).apply( BigInteger.valueOf( 100 ) ) ;
        System.out.println( result );
    }
}

不过老实说，引入了lambda之后确实简洁了不少。这里简单解释一下。首先还是做β变换：

((Improver<T>)f -> f.apply( f )).apply( f -> r.apply( x -> f.apply( f ).apply( x ) ) );
(f -> r.apply( x -> f.apply( f ).apply( x ) )).apply( f -> r.apply( x -> f.apply( f ).apply( x ) ) );

其实也不用过多解释了，这样的形式已经和Y组合子的定义一致了。

WolframScript真魔法

由于纯函数支持类scala的占位符_，所以ws写出来真是又简洁又看不懂。（代码来自互联网）

yCombinator@f_ := #@# &[Function[n, f[#@#]@n] &];

果然还是喜欢CoffeeScript啊……