Definición de combinador Y alternativo

Question

He pasado algún tiempo pensando sobre el combinador Y últimamente, y he descubierto que generalmente se define (más o menos) de la siguiente manera (esto es en C#, pero el lenguaje de elección no es importante):

public delegate TResult SelfApplicable<TResult>(SelfApplicable<TResult> r); 

public static TResult U<TResult>(SelfApplicable<TResult> r) 
{ 
    return r(r); 
} 

public static Func<TArg1, TReturn> Y<TArg1, TReturn>(Func<Func<TArg1, TReturn>, Func<TArg1, TReturn>> f) 
{ 
    return U<Func<TArg1, TReturn>>(r => arg1 => f(U(r))(arg1)); 
} 

Mientras que eso es perfectamente funcional (nunca mejor dicho), parecería que mi definición es mucho más simple:

public static Func<TArg1, TReturn> Y<TArg1, TReturn>(Func<Func<TArg1, TReturn>, Func<TArg1, TReturn>> f) 
{ 
    return f(n => Y(f)(n)); 
} 

¿hay alguna razón por la cual este último definición no es tan común (todavía tengo que encontrarlo en la red)? ¿Tal vez tendría algo que ver con la definición de Y en términos de sí mismo?

Answer 1

Haskell Curry inventó el combinador Y para definir y utilizar las funciones recursivas anónimos en el cálculo lambda sin tipo, que se define de la siguiente manera:
Y = λf·(λx·f (x x)) (λx·f (x x))

Mi definición en contra del propósito original del combinador Y ya que confía en el soporte inherente de C# para definir funciones recursivas. Sin embargo, sigue siendo útil ya que permite definir funciones recursivas anónimas en C#.

Answer 2

No estoy seguro de cuál es tu pregunta, pero supongo que la razón por la que ni el combinador Y ni su solución se observan tanto en la naturaleza es doble:

1. funciones recursivas anónimos son muy raros; en particular, dado que C# no tiene una gran compatibilidad (lectura: ninguna) para la recursividad final.

2. Hay una mucho más fácil (más fácil de leer para los no iniciados) forma de definir pseudo lambdas recursivos “anónimos” en C#:

   Func<int, int> fac = null; 
   fac = x => x == 0 ? 1 : fac(x - 1) * x; 
   

   Por supuesto, esto es no anónima pero es “suficientemente cerca” para propósitos prácticos.

Answer 3

Anónimo recursividad, es decir, con un punto combinador fijo, no se ve a menudo en los imperativos idiomas, de tipo fuerte, por la sencilla razón de que es más fácil de nombrar a su función [censurado] que de definir un anónimo función que realiza la misma tarea. Además, OOA & D nos enseña que el código que tiene valor en varios lugares no debe duplicarse; debe ser nombrado y, por lo tanto, accesible desde un lugar común. Las lambdas son, por su propia naturaleza, únicas; una forma de especificar unas pocas líneas de código específico de situación para usar en un algoritmo más general, como construcciones de bucle. La mayoría de los algoritmos recursivos son cosas que tienen una aplicación bastante general (ordenación, generación de series recursivas, etc.), que generalmente los llevan a ser más accesibles.

Cálculo lambda aparte, en la mayoría de los lenguajes de programación debe existir una función anónima F antes de que pueda ser utilizada. Eso imposibilita la definición de una función en términos de sí misma.En algunos lenguajes funcionales tales como Erlang, la función F se define utilizando "sobrecarga", donde se utilizan las funciones más simples como casos base para los más complejos:

Fact(0) -> 1 

Fact(i) -> Fact(i-1) * i 

Esto estaría bien, excepto que en Erlang-mundo esta ahora es una función llamada "Fact", y cuando se llama a ese método, el programa "caerá" a través de las sobrecargas hasta que encuentre el primero para el que coinciden los parámetros. No hay un equivalente en C# para este constructo exacto porque C# no admite la elección de una sobrecarga basada en el valor.

El truco consiste en obtener de alguna manera una referencia a la función que se puede pasar a la función. Hay muchas formas, todas las cuales requieren una referencia preexistente EN ALGÚN LUGAR. Si no puede hacer referencia a la función por su nombre, entonces el tipo de la función FP-combinator es Func<Func<Func<Func<Func<.... El método de Konrad es el más fácil, pero en C# termina como un truco (se compila, pero ReSharper todavía se queja de que es una posible InvalidOperationException, no puede invocar un puntero de método nulo).

Aquí es algo que utilizo para los casos simples, básicamente utilizando la solución delegado por no ser capaz de escribir de forma implícita una lambda escrito implícitamente-:

public static class YCombinator 
{ 
    public delegate TOut RLambda<TIn, TOut>(RLambda<TIn, TOut> rLambda, TIn a); 
    public static Func<T,T> Curry<T>(this RLambda<T,T> rLambda) 
    { 
     return a => rLambda(rLambda, a); 
    } 
} 

//usage 
var curriedLambda = YCombinator.Curry<int>((f, i) => i <= 0 ? 1 : f(f, i - 1)*i) 
var shouldBe120 = curriedLambda(5); 

Puede declarar una sobrecarga Curry<TIn, TOut> para manejar los casos en que el tipo de entrada no es el tipo de salida, como producir una lista de los primeros N números primos; esa función P puede definirse recursivamente como la función que produce una lista de todos los enteros positivos que no son divisibles por ningún número primo menor. El punto fijo P (1) => 2 define un caso base desde la cual se puede definir un algoritmo recursivo (aunque no muy eficiente):

var curriedLambda = 
      YCombinator.Curry<int, List<int>>(
       (p, i) => i == 1 
           ? new List<int>{2} 
           : p(p, i - 1) 
            .Concat(new[] 
               { 
                Enumerable.Range(p(p, i - 1)[i - 2], 
                    int.MaxValue - p(p, i - 1)[i - 2]) 
                 .First(x => p(p, i - 1).All(y => x%y != 0)) 
               }).ToList() 
       ); 
     Assert.AreEqual(new []{2,3,5,7,11}, curriedLambda(5)); 

Y así el enigma se presenta; aunque ciertamente PUEDE definir todo como una función de orden superior, este buscador principal sería MUCHO más rápido si se definiera imperativamente en lugar de funcionalmente. La aceleración principal es simplemente definir p (p, i-1) en cada nivel, por lo que no se evalúa 3 veces por nivel de recursión. Un lenguaje más inteligente diseñado para funcionar funcionalmente lo haría por usted.