各语言Y组合子大比拼

微信扫一扫,分享到朋友圈

各语言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 {
    private interface Improver {
        Function apply( Improver f ) ;
    }
 
    private Function Y( final Function<Function,Function> r ) {
        return ((Improver)f -> f.apply( f )).apply( f -> r.apply( x -> f.apply( f ).apply( x ) ) ) ;
    }
 
    public static void main( String[] args ) {
        YCombinatorFactorial yf = new YCombinatorFactorial() ;
        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)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啊……

中国电信开通雄安、上海、深圳等多地5G独立组网试点

上一篇

GeForce cards mysteriously begin playing nice with TR's FreeSync monitors

下一篇

你也可能喜欢

各语言Y组合子大比拼

长按储存图像,分享给朋友