Combinador de golf de punto fijo

9

Escriba un combinador de punto fijo en la menor cantidad de caracteres posible, en el idioma que elija.

  • forma libre ( es decir , lo que sea más corto): programa completo, función real, fragmento de código
  • no puede usar su biblioteca estándar si tiene una
  • Sin embargo, puede extraerlo de otras funciones de alto nivel si prefiere hacerlo antes que construirlo desde las bases

Incluya un factorial recursivo o Fibonacci que lo use como demostración.

En esta pregunta, la autorreferencia es aceptable, el objetivo es únicamente eliminarla de la función recursiva a la que se aplicará.

JB
fuente
¿Está bien una implementación en lenguaje perezoso? (¿Aceptarías (define Y(lambda(f)(f(Y f))))?)
Eelvex
Cualquier implementación que pueda demostrar con uno de los ejemplos solicitados está bien.
JB
1
Si no me equivoco, estrictamente hablando, el término "combinador Y" se refiere específicamente a un único combinador de punto fijo descubierto por Haskell Curry, λf. (Λx.f (xx)) (λx.f (xx)).
Joey Adams
@Eelvex: Obviamente, ambas respuestas hasta ahora (incluida la propia respuesta del OP) utilizan la forma de hacer trampa, así que supongo que eso está bien. :-P Personalmente, prefiero seguir el enfoque de @ Joey y decir que solo el combinador Y real (no autorreferencial) funcionará. ;-)
Chris Jester-Young
@ Chris: Oh, Dios mío. Eso es lo que tenía en mente al principio, y luego ... me olvidé en el camino. Es demasiado tarde para cambiar ahora, tendremos que abrir otra pregunta.
JB

Respuestas:

13

Haskell: 10 personajes

y f=f$y f

Ejemplo de uso para crear definiciones recursivas de factorial o 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]

Sin embargo, una forma más común de usar ysería generar estas secuencias directamente, en lugar de como funciones:

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

Por supuesto, con Haskell, ¡esto es como disparar a un pez en un barril! La Data.Functionbiblioteca tiene esta función, llamada fix, aunque implementada de manera algo más detallada.

MtnViewMark
fuente
4

Perl, 37

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

Demostración factorial:

sub fact {
  my ($r, $n) = @_;
  return 1 if $n < 2;
  return $n * $r->($n-1);
}
print "Factorial $_ is ", f(\&fact)->($_), "\n" for 0..10;

Demostración de Fibonacci:

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;
JB
fuente
3

GNU C - 89 caracteres

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

Ejemplo:

#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;
}
Joey Adams
fuente
1

k2, 12 char

La implementación autorreferencial obvia es la más corta. Esta es una señal de buen diseño del lenguaje. Desafortunadamente, K no es perezoso, por lo que solo podemos administrar la llamada por valor.

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

Esta definición también debería funcionar en k4 y q sin problemas, aunque supongo que k2 para los ejemplos a continuación.

  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

Unos 18 caracteres más modestos nos permiten transcribir exactamente (λx. x x) (λxyz. y (x x y) z)a K.

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

Tal vez algún día (k7?), Esto podría parecer Y:{x Y x}.

Algoritmo de tiburón
fuente
0

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

Créditos: https://gist.github.com/WoLpH/17552c9508753044e44f

Labo
fuente
Python 3 tiene filtro. También lamento haber descuidado marcar ese comentario como una broma
Cyoce
El filtro de Python 3 devuelve un objeto de filtro y no una lista. Sería menos legible o pitónico usar filtro.
Labo
sería menos pitónico, pero más en línea era la programación funcional , que era mi punto
Cyoce,