各语言Y组合子大比拼

栏目: Python · 发布时间: 6年前

内容简介:最近有点无聊,突然想试试在各种语言里面实现Y组合子。不过写完之后,没想到结果完全出乎我的意料。嘛,让我们来看看不同语言里的Y组合子。首先祭上Y组合子的定义:Y = \lambda f. (\lambda x. f(x \, x)) \, (\lambda x. f(x \, x))

最近有点无聊,突然想试试在各种语言里面实现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魔法

大部分如 luaphp 和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啊……


以上所述就是小编给大家介绍的《各语言Y组合子大比拼》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

编程真好玩

编程真好玩

[英] 乔恩·伍德科克 / 余宙华 / 南海出版公司 / 2017-8-1 / 88.00元

在美国,编程已进入幼儿园和中小学课堂,是备受欢迎的课程之一。 在英国,编程被列入国家教学大纲,成为6~15岁孩子的必修课。 在芬兰,编程理念融入了小学的各门课程,孩子们可以随时随地学编程。 编程已经成为世界的通用语言,和听、说、读、写、算一样,是孩子必须掌握的技能。 Scratch是美国麻省理工学院设计开发的可视化少儿编程工具,全球1500多万孩子正在学习使用。它把枯燥乏味......一起来看看 《编程真好玩》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码