¿Qué es un combinador en Y? [cerrado]

Un combinador en Y es un concepto informático desde el lado “funcional” de las cosas. La mayoría de los programadores no saben mucho sobre combinadores, si es que han oído hablar de ellos.

• ¿Qué es un combinador en Y?
• ¿Cómo funcionan los combinadores?
• ¿Para qué son buenos?
• ¿Son útiles en lenguajes procesales?

Sep 18 '08 22:09 Chris Ammerman

Si está listo para una lectura larga, Mike Vanier tiene una excelente explicación . En pocas palabras, le permite implementar la recursividad en un lenguaje que no necesariamente lo admite de forma nativa.

Sep 18 '2008 15:09 Nicholas Mancuso

Saqué esto de http://www.mail-archive.com/[email protected] /msg02716.html , que es una explicación que escribí hace varios años.

Usaré JavaScript en este ejemplo, pero muchos otros lenguajes también funcionarán.

Nuestro objetivo es poder escribir una función recursiva de 1 variable usando solo funciones de 1 variable y sin asignaciones, definiendo cosas por nombre, etc. (Por qué este es nuestro objetivo es otra pregunta, tomemos esto como el desafío que 'se dan.) Parece imposible, ¿eh? Como ejemplo, implementemos factorial.

Bueno, el paso 1 es decir que podríamos hacer esto fácilmente si hiciéramos un poco de trampa. Usando funciones de 2 variables y asignación, al menos podemos evitar tener que usar la asignación para configurar la recursividad.

// Here's the function that we want to recurse.
X = function (recurse, n) {
  if (0 == n)
    return 1;
  else
    return n * recurse(recurse, n - 1);
};

// This will get X to recurse.
Y = function (builder, n) {
  return builder(builder, n);
};

// Here it is in action.
Y(
  X,
  5
);

Ahora veamos si podemos hacer menos trampas. Bueno, en primer lugar estamos usando la asignación, pero no es necesario. Podemos simplemente escribir X e Y en línea.

// No assignment this time.
function (builder, n) {
  return builder(builder, n);
}(
  function (recurse, n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse, n - 1);
  },
  5
);

Pero estamos usando funciones de 2 variables para obtener una función de 1 variable. ¿Podemos arreglar eso? Bueno, un tipo inteligente llamado Haskell Curry tiene un buen truco: si tienes buenas funciones de orden superior, entonces solo necesitas funciones de 1 variable. La prueba es que puedes pasar de funciones de 2 (o más en el caso general) variables a 1 variable con una transformación de texto puramente mecánica como esta:

// Original
F = function (i, j) {
  ...
};
F(i,j);

// Transformed
F = function (i) { return function (j) {
  ...
}};
F(i)(j);

donde... sigue siendo exactamente igual. (Este truco se llama "curry" en honor a su inventor. El lenguaje Haskell también lleva el nombre de Haskell Curry. Archívelo en trivia inútil). Ahora simplemente aplique esta transformación en todas partes y obtendremos nuestra versión final.

// The dreaded Y-combinator in action!
function (builder) { return function (n) {
  return builder(builder)(n);
}}(
  function (recurse) { return function (n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse)(n - 1);
  }})(
  5
);

No dudes en probarlo. alert() ese retorno, átelo a un botón, lo que sea. Ese código calcula factoriales, de forma recursiva, sin utilizar asignaciones, declaraciones o funciones de 2 variables. (Pero tratar de rastrear cómo funciona probablemente le haga girar la cabeza. Y entregarlo, sin la derivación, ligeramente reformateado dará como resultado un código que seguramente desconcertará y confundirá).

Puedes reemplazar las 4 líneas que definen recursivamente factorial con cualquier otra función recursiva que desees.

Jul 15 '2011 21:07 btilly

Me pregunto si tiene alguna utilidad intentar construir esto desde cero. Vamos a ver. Aquí hay una función factorial recursiva básica:

function factorial(n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}

Refactoricemos y creemos una nueva función llamada factque devuelva una función de cálculo factorial anónima en lugar de realizar el cálculo en sí:

function fact() {
    return function(n) {
        return n == 0 ? 1 : n * fact()(n - 1);
    };
}

var factorial = fact();

Es un poco raro, pero no tiene nada de malo. Simplemente estamos generando una nueva función factorial en cada paso.

La recursividad en esta etapa sigue siendo bastante explícita. La factfunción debe conocer su propio nombre. Parametricemos la llamada recursiva:

function fact(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
}

function recurser(x) {
    return fact(recurser)(x);
}

var factorial = fact(recurser);

Eso es genial, pero recurseraún necesita saber su propio nombre. Parametricémoslo también:

function recurser(f) {
    return fact(function(x) {
        return f(f)(x);
    });
}

var factorial = recurser(recurser);

Ahora, en lugar de llamar recurser(recurser)directamente, creemos una función contenedora que devuelva su resultado:

function Y() {
    return (function(f) {
        return f(f);
    })(recurser);
}

var factorial = Y();

Ahora podemos deshacernos del recursernombre por completo; es solo un argumento para la función interna de Y, que puede reemplazarse con la función misma:

function Y() {
    return (function(f) {
        return f(f);
    })(function(f) {
        return fact(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y();

El único nombre externo al que aún se hace referencia es fact, pero ya debería quedar claro que también se puede parametrizar fácilmente, creando una solución completa y genérica:

function Y(le) {
    return (function(f) {
        return f(f);
    })(function(f) {
        return le(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y(function(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
});

Jul 15 '2011 23:07 Wayne