Golfed fixed point combinator

9

3

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.

J B

Posted 2011-02-19T14:04:11.040

Reputation: 9 638

Is a lazy-language implementation ok? (Would you accept (define Y(lambda(f)(f(Y f)))) ?) – Eelvex – 2011-02-19T20:28:44.843

Any implementation you can demonstrate with one of the requested examples is ok. – J B – 2011-02-19T21:52:40.547

1If 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)) . – Joey Adams – 2011-02-20T01:32:49.400

@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. ;-) – Chris Jester-Young – 2011-02-20T02:21:09.093

@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. – J B – 2011-02-20T11:06:52.487

Answers

13

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.

MtnViewMark

Posted 2011-02-19T14:04:11.040

Reputation: 4 779

4

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;

J B

Posted 2011-02-19T14:04:11.040

Reputation: 9 638

3

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;
}

Joey Adams

Posted 2011-02-19T14:04:11.040

Reputation: 9 929

1

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}.

algorithmshark

Posted 2011-02-19T14:04:11.040

Reputation: 8 144

0

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

Labo

Posted 2011-02-19T14:04:11.040

Reputation: 229

Python 3 has filter. Also I'm sorry I neglected to mark that comment as a joke – Cyoce – 2016-05-05T22:50:56.500

Python 3 's filter returns a filter object and not a list. It would be less readable or pythonic to use filter. – Labo – 2016-05-06T09:33:37.130

it would be less Pythonic, but more in line was [tag:functional-programming], which was my point – Cyoce – 2016-05-06T17:49:16.203