# 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=$_[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;


## 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[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]))

• 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

# APL (Dyalog Unicode), 9 bytes

{∇(⍎⍺⍺)⍵}


Try it online!

An operator whose left operand is a string representing the function to be combinatorified and whose right argument is passed to the function once it is combinatorised. I think it's okay to pass the function as a string, but if not, I will delete this answer.

Explanation

{∇(⍎⍺⍺)⍵}
∇(⍎⍺⍺)     ⍝ Equivalent to f ( Fix f )
⍺⍺      ⍝ Left operand
⍎        ⍝ Evaluate to get monadic operator
∇           ⍝ Self-reference (Fix f). Pass as operand to f (or ⍎⍺⍺)
⍵    ⍝ Apply the derived function to the right argument ⍵


# Wolfram Language (Mathematica), 16 bytes

v_//Z@g_=Z@g~g~v           (* golfed   *)
Z[g_][v_] = g[Z[g],v]      (* ungolfed *)


Try it online!

This definition of the Z combinator uses the Wolfram Language's pattern-matching to make sure that any expression of the form Z[g] remains unevaluated as long as the second argument is missing; only the two-argument form Z[g][v] matches the above pattern and is replaced by g[Z[g],v], which in turn contains the single-argument form Z[g] that remains unevaluated until later. This distinction between an inert single-argument form Z[g] and an automatically-substituted two-argument form Z[g][v] allows for a controlled recursion process that remains tied to the application of the second argument.

## examples

### factorial

fac[r_, n_] = If[n==0, 1, n*r[n-1]];
Table[Z[fac][i], {i, 0, 10}]
(*    {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800}    *)


Same with an anonymous function:

Table[Z[If[#2==0, 1, #2*#1[#2-1]]&][i], {i, 0, 10}]
(*    {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800}    *)


Same but using Mathematica's built-in self-reference operator #0: we don't actually need a combinator to define recursive anonymous functions,

Table[If[#1==0, 1, #1*#0[#1-1]]&[i], {i, 0, 10}]
(*    {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800}    *)


### Fibonacci sequence

fib[r_, n_] = If[n<=1, n, r[n-2]+r[n-1]];
Table[Z[fib][i], {i, 0, 10}]
(*    {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55}    *)