Y-Combinator Ejemplo Práctico

Question

He estado leyendo un poco últimamente acerca de la programación funcional y estoy tratando de asimilar la Y-Combinator. Tengo entendido que se puede utilizar la Y-Combinator para aplicar eficazmente la recursividad en un idioma que no es compatible recursión directa. Sin embargo, todos los idiomas que tengo tendencia a utilizar ya es compatible con la recursividad así que no estoy seguro de lo útil que sería el uso de la Y-Combinator para eso.

¿Hay una mejor ejemplo práctico de uso de Y-Combinator que me falta? Ha hecho nadie usa uno de cada código de producción real? O si está utilizando la Y-Combinator realmente sólo un ejercicio académico endiablada (aunque sea muy bien).

Answer 1

Voy a estar en desacuerdo con otras respuestas: El punto fijo (Y) combinador hace tener aplicaciones prácticas , pero se necesita una mente muy imaginativa para encontrarlos . Al igual que Bruce McAdam. Aquí está el resumen de su papel Eso Sobre lo envuelve :

  

El combinador Y para el cálculo de puntos fijos se puede expresar en Standard ML. Se utiliza con frecuencia como un ejemplo de la potencia de funciones de orden superior, pero no se considera generalmente como una construcción de programación útil. A continuación, vamos a ver cómo una técnica de programación basado en el combinador Y y envolturas puede dar a los programadores un nivel de control sobre el funcionamiento interno de las funciones de otro modo no es posible sin tener que reescribir y recompilar el código. Como un experimento, el algoritmo de tipo inferencia W se implementa utilizando esta técnica, de modo que los mensajes de error se producen con una interferencia mínima para el algoritmo. El código de este programa de ejemplo ilustra la verdadera utilidad de los conceptos y la facilidad con que se pueden aplicar. También se discuten una serie de otras técnicas de implementación y posibles aplicaciones, incluyendo el uso de funciones de orden superior para simular el uso de excepciones y continuaciones.

Es un gran papel; cualquier persona interesada en la programación funcional, probablemente disfrutará de la lectura.

Answer 2

Usted puede comprobar a cabo este post ingeniosa en la implementación de la Y Combinator en C #: recursivas Lambda Expresiones , que podría ayudar a entender mejor la idea.

Es posible que desee echa un vistazo a algunos artículos agradables en Wikipedia: punto fijo combinador y < a href = "http://en.wikipedia.org/wiki/Fixed-point_theorem#Fixed_point_theorems_in_discrete_mathematics_and_theoretical_computer_science" rel = "nofollow noreferrer"> fijo teoremas de punto

Como dice Nathan, muchas técnicas funcionales están relacionados con el combinador Y y son útiles, por lo que mantiene en él! Y realmente es útil, ya que le permite entender su código mejor, pero no creo que es un especialmente útil para describir cómo ayuda.

Answer 3

Se puede pensar en el combinador como la máquina virtual que se ejecuta su función, lo que usted describe por una (= función de orden superior) funcional no recursivo.

A veces sería bueno tener este combinador bajo control de programa, para hacer cosas similares como la programación orientada a aspectos (memoizing, seguimiento, ...), pero ningún lenguaje de programación que conozco lo permite. Probablemente sería demasiado engorroso mayor parte del tiempo y / o demasiado difícil de aprender.

Answer 4

Otros me pueden corregir si me equivoco, pero estoy bastante seguro de que el combinador Y es estrictamente académico. Piense en esto: para ponerlo en práctica su idioma necesita para apoyar las funciones de orden superior, pero no recursividad. Sólo hay un lenguaje conocido como eso:. Cálculo lambda

Así que hasta nuestros mecanismos de cambio de las máquinas de Turing que se ejecuta en el cálculo lambda, el combinador Y será estrictamente académico.

Nota: otras técnicas funcionales relacionados con el combinador Y son útil, por lo que mantener a la misma. Comprender el combinador Y le ayudará a entender las continuaciones, la evaluación perezosa, etc.

Answer 5

let sprite = pipe4 sprite_start blanks (manyTill attribute newline) blanks (fun a b c _ -> Sprite(a,c))

let sprites = 
    let rec y f x = f (y f) x // The Y Combinator
    //let rec sprites_up = many1Indents sprite sprites_up |>> (fun x -> SubSprites x) // Does not work.
    let sprites_up = y (fun f -> many1Indents sprite f |>> (fun x -> SubSprites x))
    many1Indents sprite sprites_up

A continuación se muestra un ejemplo del compilador para una biblioteca de juegos bien pequeño que estoy haciendo en F #. Más específicamente, en lo anterior tengo que tener la forma recursiva sprites_up llamarse de otro modo el analizador muesca no funcionaría correctamente.

Sin el Y Combinator, no podría haber hecho el analizador adecuadamente y habría tenido que recurrir a escribir algo como esto:

let sprites_up4 = many1Indents sprite error |>> (fun x -> SubSprites x) 
let sprites_up3 = many1Indents sprite sprites_up4 |>> (fun x -> SubSprites x) 
let sprites_up2 = many1Indents sprite sprites_up3 |>> (fun x -> SubSprites x) 
let sprites_up1 = many1Indents sprite sprites_up2 |>> (fun x -> SubSprites x) 
let sprites_up = many1Indents sprite sprites_up1 |>> (fun x -> SubSprites x) 

No habría sido una gran solución, la Y Combinator realmente me salvó allí. Ciertamente no fue lo primero que vino a la mente sin embargo.