# Golfed fixed point combinator

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.

• Is a lazy-language implementation ok? (Would you accept (define Y(lambda(f)(f(Y f)))) ?) – Eelvex Feb 19 '11 at 20:28
• Any implementation you can demonstrate with one of the requested examples is ok. – J B Feb 19 '11 at 21:52
• 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)) . – Joey Adams Feb 20 '11 at 1:32
• @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 Feb 20 '11 at 2:21
• @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 Feb 20 '11 at 11:06

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. ## Perl, 37 sub f{my$s=$_;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;


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


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

# 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])
+ [y for y in x if x == y]
+ f([item for item in x if item > x])
) if x
else []
)
print(quicksort([1, 3, 5, 4, 1, 3, 2]))

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