Wednesday, 17 March 2010

Y-combinators

Y-combinators are strange and very crazy things. Below is little collection.

Perl

sub Y {
    my ( $curried_rec ) = @_;
    sub {
        my ( $f1 ) = @_;
        $curried_rec->( sub { $f1->( $f1 )->( @_ ) } )
    }->( sub {
        my ( $f2 ) = @_;
        $curried_rec->( sub { $f2->( $f2 )->( @_ ) } )
    } )
}

print Y( sub {
    my ( $rec ) = @_;
    sub {
        my ( $n ) = @_;
        $n < 2 ? 1 : $n * $rec->( $n - 1 );
    }
} )->( 5 );

JavaScript

function Y(le) {
    return (function (f) {
        return f(f);
    }(function (f) {
        return le(function (x) {
            return f(f)(x);
        });
    }));
}

var factorial = Y(function (fac) {
    return function (n) {
        return n <= 2 ? n : n * fac(n - 1);
    };
});

var number120 = factorial(5);

No comments:

Post a Comment

Post a Comment