9
\$\begingroup\$

Write a fixed point combinator in as few characters as possible, in the language of your choice.

  • free form (i.e., whatever's shortest): whole program, actual function, code snippet
  • you may not use your standard library's if it has one
  • you may however extract it from other high-level functions it you'd rather do that than construct it from the bases

Please include a recursive factorial or Fibonacci that uses it as a demo.

In this question, self-reference is acceptable, the aim is solely to remove it from the recursive function it will apply to.

\$\endgroup\$
  • \$\begingroup\$ Is a lazy-language implementation ok? (Would you accept (define Y(lambda(f)(f(Y f)))) ?) \$\endgroup\$ – Eelvex Feb 19 '11 at 20:28
  • \$\begingroup\$ Any implementation you can demonstrate with one of the requested examples is ok. \$\endgroup\$ – J B Feb 19 '11 at 21:52
  • 1
    \$\begingroup\$ If I'm not mistaken, strictly speaking, the term "Y combinator" refers specifically to a single fixpoint combinator discovered by Haskell Curry, λf.(λx.f (x x)) (λx.f (x x)) . \$\endgroup\$ – Joey Adams Feb 20 '11 at 1:32
  • \$\begingroup\$ @Eelvex: Obviously both answers so far (including the OP's own answer) use the cheating way, so, I guess that makes it okay. :-P Personally, I'd rather go with @Joey's approach and say that only the real (non-self-referential) Y combinator will do. ;-) \$\endgroup\$ – Chris Jester-Young Feb 20 '11 at 2:21
  • \$\begingroup\$ @Chris: Oh my. That's what I had in mind initially, and then I... forgot along the way. It's kind of too late to change now, we'll have to open another question. \$\endgroup\$ – J B Feb 20 '11 at 11:06
12
\$\begingroup\$

Haskell: 10 characters

y f=f$y f

Example of use to create recursive definitions of factorial or nth-Fibonacci:

> map ( y(\f n->if n <= 1 then 1 else n*f(n-1)) ) [1..10]
[1,2,6,24,120,720,5040,40320,362880,3628800]

> map ( y(\f n->if n <= 1 then 1 else f(n-1)+f(n-2)) ) [0..10]
[1,1,2,3,5,8,13,21,34,55,89]

Though, a more common way to use y would be to generate these sequences directly, rather than as functions:

> take 10 $ y(\p->1:zipWith (*) [2..] p)
[1,2,6,24,120,720,5040,40320,362880,3628800]

> take 11 $ y(\f->1:1:zipWith (+) f (tail f))
[1,1,2,3,5,8,13,21,34,55,89]

Of course, with Haskell, this is a bit like shooting fish in a barrel! The Data.Function library has this function, called fix, though implemented somewhat more verbosely.

\$\endgroup\$
4
\$\begingroup\$

Perl, 37

sub f{my$s=$_[0];sub{$s->(f($s),@_)}}

Factorial demonstration:

sub fact {
  my ($r, $n) = @_;
  return 1 if $n < 2;
  return $n * $r->($n-1);
}
print "Factorial $_ is ", f(\&fact)->($_), "\n" for 0..10;

Fibonacci demonstration:

sub fib {
  my ($r, $n) = @_;
  return 1 if $n < 2;
  return $r->($n-1) + $r->($n-2);
}
print "Fibonacci number $_ is ", f(\&fib)->($_), "\n" for 0..10;
\$\endgroup\$
3
\$\begingroup\$

GNU C - 89 chars

#define fix(f,z)({typeof(f)__f=(f);typeof(__f(0,z))x(typeof(z)n){return __f(x,n);}x(z);})

Example:

#define lambda2(arg1, arg2, expr) ({arg1;arg2;typeof(expr)__f(arg1,arg2){return(expr);};__f;})

int main(void)
{
    /* 3628800 */
    printf("%ld\n", fix(lambda2(
        long factorial(int n), int n, 
            n < 2 ? 1 : n * factorial(n-1)
        ), 10));

    /* 89 */
    printf("%ld\n", fix(lambda2(
        long fibonacci(int n), int n, 
            n < 2 ? 1 : fibonacci(n-1) + fibonacci(n-2)
        ), 10));

    return 0;
}
\$\endgroup\$
1
\$\begingroup\$

k2, 12 char

The obvious self-referential implementation is the shortest. This is a sign of good language design. Unfortunately, K isn't lazy, so we can only manage call-by-value.

Y:{x[Y[x]]y}

This definition should also work in k4 and q without trouble, though I assume k2 for the examples below.

  Y:{x[Y[x]]y}
  fac: {[f;arg] :[arg>0; arg*f[arg-1]; 1]}
  Y[fac] 5
120
  fib: {[f;arg] :[arg>1; f[arg-1] + f[arg-2]; arg]}
  Y[fib]' !10
0 1 1 2 3 5 8 13 21 34

A more modest 18 characters lets us exactly transcribe (λx. x x) (λxyz. y (x x y) z) into K.

{x[x]}{y[x[x;y]]z}

Maybe someday (k7?), this could look like Y:{x Y x}.

\$\endgroup\$
0
\$\begingroup\$

Python 3, 30 Bytes

Y=lambda f:lambda a:f(Y(f))(a)

Demo :

Y=lambda f:lambda a:f(Y(f))(a)
quicksort = Y(
lambda f:
    lambda x: (
        f([item for item in x if item < x[0]])
        + [y for y in x if x[0] == y]
        + f([item for item in x if item > x[0]])
    ) if x
    else []
)
print(quicksort([1, 3, 5, 4, 1, 3, 2]))

Credits : https://gist.github.com/WoLpH/17552c9508753044e44f

\$\endgroup\$
  • \$\begingroup\$ Python 3 has filter. Also I'm sorry I neglected to mark that comment as a joke \$\endgroup\$ – Cyoce May 5 '16 at 22:50
  • \$\begingroup\$ Python 3 's filter returns a filter object and not a list. It would be less readable or pythonic to use filter. \$\endgroup\$ – Labo May 6 '16 at 9:33
  • \$\begingroup\$ it would be less Pythonic, but more in line was functional-programming, which was my point \$\endgroup\$ – Cyoce May 6 '16 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.