Skip to content

Instantly share code, notes, and snippets.

@ironcamel
Created March 25, 2012 18:43
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save ironcamel/2198958 to your computer and use it in GitHub Desktop.
Recursive closure
my $factorial = sub {
my $val = shift;
return $val * __SUB__->($val - 1) if $val > 1;
return $val;
};
print $factorial->(5);
@oylenshpeegul
Copy link

I guess we'd do it in Ruby with one more level of indirection?

factorial = lambda { |val|
    lambda { |me|
      me.call(me, val)
    }.call(
        lambda{ |sub, val|
            return val * sub.call(sub, val - 1) if val > 1
            return val
        }
    )
}

puts factorial.call(5)

@ironcamel
Copy link
Author

Is there no way to do this in Ruby with only 1 lambda?

@oylenshpeegul
Copy link

Not that I know of. This is pretty much what we would have done in Perl before __SUB__, right?

sub Y {
    my ($proc, @args) = @_;
    $proc->($proc, @args);
}

my $factorial = sub {
    my $val = shift;
    Y(sub {
          my($sub, $val) = @_;
          return $val * $sub->($sub, $val - 1) if $val > 1;
          return $val;
      },
      $val,
    )
};


say $factorial->(5);

I believe it's called a Y combinator.

@ironcamel
Copy link
Author

I think I finally understand what a Y-combinator is. Your example Y-combinator function is so much simpler than the examples on wikipedia!

@oylenshpeegul
Copy link

The spankin' new Functional::Utility module has a y_combinator routine!

use Functional::Utility qw(y_combinator);

my $factorial = y_combinator {
    my $val = shift;

    return sub {
        my $n = shift;
        return $n if $n == 1;
        return $n * $val->($n - 1);
    };
};

say $factorial->(5);

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment