10
\$\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\$
5
  • \$\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\$ 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
13
\$\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\$
2
\$\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\$
3
  • \$\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
0
\$\begingroup\$

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 ⍵
\$\endgroup\$
0
\$\begingroup\$

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}    *)
\$\endgroup\$

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.