Schreiben Sie einen Festkomma-Kombinator in möglichst wenigen Zeichen in der Sprache Ihrer Wahl.

• freie Form ( dh was auch immer am kürzesten ist): gesamtes Programm, tatsächliche Funktion, Code-Snippet
• Sie dürfen Ihre Standardbibliotheken nicht verwenden, wenn sie eine haben
• Sie können es jedoch aus anderen übergeordneten Funktionen extrahieren, wenn Sie dies lieber tun, als es aus den Basen zu konstruieren

Bitte fügen Sie eine rekursive Fakultät oder Fibonacci hinzu, die sie als Demo verwendet.

In dieser Frage ist eine Selbstreferenz akzeptabel. Das Ziel besteht ausschließlich darin, sie aus der rekursiven Funktion zu entfernen, für die sie gelten wird.

Haskell: 10 Zeichen

y f=f$y f

Anwendungsbeispiel zum Erstellen rekursiver Definitionen von Fakultäts- oder n-ten 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]

Eine gebräuchlichere Methode ywäre jedoch, diese Sequenzen direkt und nicht als Funktionen zu generieren:

> 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]

Bei Haskell ist das natürlich ein bisschen so, als würde man Fische in einem Fass schießen! Die Data.FunctionBibliothek hat diese Funktion, die aufgerufen wird fix, obwohl sie etwas ausführlicher implementiert ist.

Perl, 37

sub f{my$s=$_[0];sub{$s->(f($s),@_)}}

Faktorielle 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 Zeichen

#define fix(f,z)({typeof(f)__f=(f);typeof(__f(0,z))x(typeof(z)n){return __f(x,n);}x(z);})

Beispiel:

#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

Die offensichtliche selbstreferenzielle Implementierung ist die kürzeste. Dies ist ein Zeichen für gutes Sprachdesign. Leider ist K nicht faul, so dass wir Call-by-Value nur verwalten können.

Y:{x[Y[x]]y}

Diese Definition sollte auch in k4 und q problemlos funktionieren, obwohl ich für die folgenden Beispiele k2 annehme.

  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

Mit bescheideneren 18 Zeichen können wir genau (λx. x x) (λxyz. y (x x y) z)in K transkribieren .

{x[x]}{y[x[x;y]]z}

Vielleicht könnte das eines Tages (k7?) So aussehen 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]))

Credits: https://gist.github.com/WoLpH/17552c9508753044e44f