use Perl

• Re: the Y Combinator (Score:1)

  by Stevan (6065) <reversethis-{moc ... {elttil.navets}> on 2006.09.05 13:17 (#49818) Journal

  I found it was actually easier to deal with the Y combinator if you implement it in terms of the U combinator, which is just your basic fixed point combinator.

  sub U {
      my $f = shift;
      sub { $f->($f, @_) };
  }
  
  sub Y {
      my $f = shift;
      U(sub {
          my $h = shift;
          sub {
              $f->(U($h)->())->(@_)
          }
      })->();
  }

  I also recently added [perl.org] the Y and U combinators to Moose::Autobox [cpan.org], so you can just do this:.

  print sub {
      my $f = shift;
      sub {
          my $n = shift;
          return 1 if $n < 2;
          return $n * $f->($n - 1);
      }
  }->y->(10);

  and get that oh so special Ruby-ish feeling in your heart.

  - Stevan

  Reply to This

  • Re: (Score:1)

    by Aristotle (5147)

    Yes, those bits of code led to a lengthy (if anemic) discussion about Y and U a few days ago [perl.org].

    I’m still trying to wrap my head around the version you present. I think I am starting to get it, but it’s still confusing (as is any version of the Y combinator, really :-)). With the version I posted, I at least get what’s going on, even though the result is clearly much more complicated than the derivation of Y in terms of U.
    • Re: (Score:1)

      by Stevan (6065)

      Ah, I was not aware of the previous conversation. Of course all this is made moot by Perl 6 (IIRC the syntax correctly).

      sub ($n) {
          return 1 if $n < 2;
          return $n * $?SUB.($n - 1);
      }

      - Stevan