functional programming - Ejemplo práctico de Y-Combinator

functional-programming

Question

He estado leyendo un poco últimamente sobre programación funcional y estoy intentando asimilar el Y-Combinator. Entiendo que puede usar el Y-Combinator para implementar efectivamente la recursión en un idioma que no admite recursividad directamente. Sin embargo, todos los idiomas que probablemente usaré ya son compatibles con la recursión, por lo que no estoy seguro de lo útil que sería usar el Combinador Y para eso.

¿Hay algún ejemplo práctico mejor del uso de Y-Combinator que me falta? ¿Alguien ha usado uno en el código de producción real? O está usando el Y-Combinator en realidad simplemente como un ejercicio académico alucinante (aunque bastante genial).

Answer 1

Otros pueden corregirme si me equivoco, pero estoy bastante seguro de que el combinador Y es estrictamente académico. Piénselo: para implementarlo, su idioma necesita admitir funciones de orden superior pero no recurrencia. Solo hay un lenguaje que conozco así: cálculo lambda.

Entonces, hasta que nuestras máquinas cambien de máquinas Turing a ejecutadas en cálculo lambda, el combinador Y será estrictamente académico.

Nota: otras técnicas funcionales relacionadas con el combinador Y son útiles, así que sigue con esto. Comprender el combinador Y lo ayudará a comprender las continuciones, la evaluación perezosa, etc.

Answer 2

Podrías echarle un vistazo a esta publicación ingeniosa sobre la implementación del Combinador Y en C #: Expresiones recursivas de Lambda , podría ayudarte a entender mejor la idea.

Es posible que desee ver algunos buenos artículos en Wikipedia: combinador de punto fijo y teoremas de punto fijo

Como dice Nathan, muchas técnicas funcionales están relacionadas con el combinador Y y son útiles, ¡así que sigan! Y realmente es útil porque te permite entender mejor tu código, pero no creo que sea particularmente útil para describir cómo ayuda.

Answer 3

Puede pensar en el combinador como la máquina virtual que ejecuta su función, que describe mediante una función no recursiva (= función de orden superior).

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

Answer 4

Voy a estar en desacuerdo con otras respuestas: el combinador de punto fijo (Y) tiene aplicaciones prácticas , pero se necesita una mente muy imaginativa para encontrarlas. Como Bruce McAdam. Aquí está el resumen de su artículo That About Wraps it Up :

El combinador Y para calcular puntos fijos se puede expresar en ML estándar. Se usa con frecuencia como un ejemplo del poder de las funciones de orden superior, pero generalmente no se considera una construcción de programación útil. Aquí, observamos cómo una técnica de programación basada en el combinador Y y los envoltorios pueden darles a los programadores un nivel de control sobre el funcionamiento interno de las funciones que de otro modo no serían posibles sin reescribir y recompilar el código. Como experimento, el algoritmo de inferencia de tipo W se implementa utilizando esta técnica, de modo que los mensajes de error se producen con la mínima interferencia al algoritmo. El código para este programa de ejemplo ilustra la utilidad genuina de los conceptos y la facilidad con la que se pueden aplicar. También se discuten otras técnicas de implementación y posibles aplicaciones, incluido 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á al leerla.

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

Aquí hay un ejemplo del compilador de una pequeña biblioteca de juegos que estoy creando en F #. Más específicamente, en lo anterior, necesito que los sprites_up se llamen recursivamente, de lo contrario el analizador de sangría no funcionaría correctamente.

Sin Y Combinator, no podría haber hecho el analizador correctamente 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, el Y Combinator realmente me salvó allí. Sin embargo, ciertamente no fue lo primero que se le vino a la mente.