Golfed fixed point combinator

Question

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.

Answer 1

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.

Answer 2

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;

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

Answer 4

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

Answer 5

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

Answer 6

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 ⍵

Answer 7

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}    *)

Answer 8

Java 8, 104 bytes

interface C{int t(int n);}interface F{C f();}interface P{C c(F f);static F g(P p){return()->p.c(g(p));}}

Based on @user's Java answer for the related Implement Fix2 combinator challenge.

Explanation:

interface C{       // Completed Function interface
  int t(int n);}   //  Using a function that transforms a given integer

interface F{       // Function interface
  C f();}          //  A wrapper to pass the 'Completed Function' as function

interface P{       // Program interface
  C c(F f);        //  Which takes a 'Function' as argument, and returns a 'Completed Function'
  
  static F g(P p){ //  Recursive function that accepts a 'Program' as argument, and returns a 'Function'
    return()->     //   Return a new function, which wraps:
      p.c(         //    A completed call to its own 'Program' interface
       g(          //     Using a recursive call to its own function
         p));}}    //     with the given 'Program' as argument

The method to call is P::g, which takes P as argument and returns F. To obtain a completed function C from an F, we can call F::f on it. P represents the function to be fixed, and its method c takes F as argument to prevent immediate evaluation, returning a C that represents a complete function to transform a given integer n with C's t(n).

Example Fibonacci implementation:

P fix = fibonacci -> n -> n>1? fibonacci.f().t(n-1)+fibonacci.f().t(n-2) : 1;
C func = P.g(fix).f();
int result = func.t(input);

Try it online.