functional programming - Explicación de los combinadores para el trabajador

functional-programming combinators

Question

¿Qué es un combinador?

¿Es "una función o definición sin variables libres" (como se define en SO)?

O qué tal esto: de acuerdo con John Hughes en su conocido artículo sobre Arrows, "un combinador es una función que construye fragmentos de programa a partir de fragmentos de programa" , lo cual es ventajoso porque "... el programador que utiliza combinators construye gran parte del deseado programa automáticamente, en lugar de escribir cada detalle a mano ". Él continúa diciendo que el map y el filter son dos ejemplos comunes de tales combinadores.

Algunos combinators que coinciden con la primera definición:

• S
• K
• Y
• otros de Mock a Mockingbird (puedo estar equivocado, no he leído este libro)

Algunos combinators que coinciden con la segunda definición:

• mapa
• filtrar
• doblar / reducir (presumiblemente)
• cualquiera de >> =, componer, fmap ?????

No me interesa la primera definición: no me ayudaría a escribir un programa real (+1 si me convences de que estoy equivocado). Por favor, ayúdame a entender la segunda definición . Creo que el mapa, el filtro y la reducción son útiles: me permiten programar a un nivel más alto: menos errores, códigos más cortos y claros. Estas son algunas de mis preguntas específicas sobre los combinadores:

1. ¿Cuáles son más ejemplos de combinadores como mapa, filtro?
2. ¿Qué combinadores suelen implementar los lenguajes de programación?
3. ¿Cómo pueden los combinators ayudarme a diseñar una mejor API?
4. ¿Cómo diseño combinadores efectivos?
5. ¿En qué se combinan los similares en un lenguaje no funcional (por ejemplo, Java) o qué utilizan estos idiomas en lugar de los combinadores?

Actualizar

Gracias a @CA McCann, ahora tengo una mejor comprensión de los combinadores. Pero una pregunta sigue siendo un punto difícil para mí:

¿Cuál es la diferencia entre un programa funcional escrito con y un uso sin escritura de combinadores?

Sospecho que la respuesta es que la versión pesada del combinador es más corta, más clara, más general, pero agradecería una discusión más profunda, si es posible.

También estoy buscando más ejemplos y explicaciones de los combinadores complejos (es decir, más complejos que el fold ) en los lenguajes de programación comunes.

Answer 1

No me interesa la primera definición: no me ayudaría a escribir un programa real (+1 si me convences de que estoy equivocado). Por favor, ayúdame a entender la segunda definición. Creo que el mapa, el filtro y la reducción son útiles: me permiten programar a un nivel más alto: menos errores, códigos más cortos y claros.

Las dos definiciones son básicamente lo mismo. El primero se basa en la definición formal y los ejemplos que se dan son primitivos combinadores: los bloques de construcción más pequeños posibles. Pueden ayudarlo a escribir un programa real en la medida en que, con ellos, pueda construir combinators más sofisticados. Piense en combinadores como S y K como el lenguaje de máquina de una hipotética "computadora combinatoria". Las computadoras reales no funcionan de esa manera, por supuesto, así que en la práctica generalmente se implementarán operaciones de más alto nivel detrás de escena de otras maneras, pero la base conceptual sigue siendo una herramienta útil para comprender el significado de esos niveles superiores operaciones.

La segunda definición que da es más informal y sobre el uso de combinadores más sofisticados, en forma de funciones de orden superior que combinan otras funciones de varias maneras. Tenga en cuenta que si los bloques de construcción básicos son los combinadores primitivos anteriores, todo lo que se construye a partir de ellos es una función de orden superior y también un combinador. Sin embargo, en un lenguaje donde existen otras primitivas, se distingue entre cosas que son o no funciones, en cuyo caso un combinador se define típicamente como una función que manipula otras funciones de forma general, en lugar de operar en funcionan las cosas directamente.

¿Cuáles son más ejemplos de combinadores como mapa, filtro?

Demasiados para enumerar! Ambas transforman una función que describe el comportamiento en un único valor en una función que describe el comportamiento en una colección completa. También puede tener funciones que transforman solo otras funciones, como componerlas de extremo a extremo o dividir y recombinar argumentos. Puede tener combinadores que conviertan las operaciones de un solo paso en operaciones recursivas que producen o consumen colecciones. O todo tipo de otras cosas, realmente.

¿Qué combinadores suelen implementar los lenguajes de programación?

Eso va a variar bastante. Hay relativamente pocos combinadores completamente genéricos, principalmente los primitivos mencionados anteriormente, por lo que en la mayoría de los casos los combinadores tendrán conocimiento de las estructuras de datos utilizadas (incluso si esas estructuras de datos están construidas a partir de otros combinadores), en las que Por lo general, hay un puñado de combinadores "totalmente genéricos" y, luego, cualesquiera que sean las diversas formas especializadas que alguien haya decidido proporcionar. Hay un número ridículo de casos en los que las (versiones adecuadamente generalizadas de) mapear, plegar y desplegar son suficientes para hacer casi todo lo que pueda desear.

¿Cómo pueden los combinators ayudarme a diseñar una mejor API?

Exactamente como dijiste, al pensar en términos de operaciones de alto nivel y la forma en que interactúan, en lugar de detalles de bajo nivel.

Piense en la popularidad de los bucles de estilo "para cada uno" sobre las colecciones, que le permiten abstraer los detalles de la enumeración de una colección. En la mayoría de los casos, estas son solo operaciones de mapeo / plegado, y haciendo de eso un combinador (en lugar de una sintaxis incorporada) puede hacer cosas como tomar dos loops existentes y combinarlos directamente de múltiples maneras: anidar uno dentro del otro, hacer uno después del otro, y así sucesivamente - simplemente aplicando un combinador, en lugar de hacer malabarismos con un montón de código.

¿Cómo diseño combinadores efectivos?

Primero, piense qué operaciones tienen sentido con los datos que usa su programa. Luego, piense en cómo esas operaciones pueden combinarse de forma significativa de maneras genéricas, así como también en cómo las operaciones se pueden dividir en partes más pequeñas que están conectadas entre sí. Lo principal es trabajar con transformaciones y operaciones , no acciones directas. Cuando tienes una función que simplemente hace un poco de funcionalidad complicada de una manera opaca y solo escupe algún tipo de resultado predigerido, no hay mucho que puedas hacer con eso. Deje los resultados finales en el código que usa los combinadores: quiere cosas que lo lleven del punto A al punto B, no cosas que esperan ser el comienzo o el final de un proceso.

¿En qué se combinan los similares en un lenguaje no funcional (por ejemplo, Java) o qué utilizan estos idiomas en lugar de los combinadores?

Ahahahaha. Es curioso que lo preguntes, porque los objetos son en realidad cosas de orden superior, tienen algunos datos, pero también llevan un montón de operaciones, y bastante de lo que constituye un buen diseño OOP se reduce a "los objetos deberían usualmente actúan como combinators, no como estructuras de datos ".

Entonces, probablemente la mejor respuesta aquí es que en lugar de cosas similares a combinator, usan clases con muchos métodos getter y setter o campos públicos, y la lógica consiste principalmente en realizar alguna acción opaca y predefinida.