Explicación de combinadores para el trabajador.

93

¿Qué es un combinador?

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

O qué tal esto: según 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 usa combinadores construye gran parte de los programa automáticamente, en lugar de escribir todos los detalles a mano ". Continúa diciendo que mapy filterson dos ejemplos comunes de tales combinadores.

Algunos combinadores que coinciden con la primera definición:

Algunos combinadores que coinciden con la segunda definición:

  • mapa
  • filtrar
  • plegar / reducir (presumiblemente)
  • cualquiera de >> =, compose, fmap ?????

No me interesa la primera definición; esas no me ayudarían a escribir un programa real (+1 si me convences de que estoy equivocado). Ayúdame a comprender la segunda definición . Creo que mapear, filtrar y reducir son útiles: me permiten programar en un nivel superior: menos errores, código más corto y claro. Estas son algunas de mis preguntas específicas sobre combinadores:

  1. ¿Cuáles son más ejemplos de combinadores como mapa, filtro?
  2. ¿Qué combinadores implementan a menudo los lenguajes de programación?
  3. ¿Cómo pueden ayudarme los combinadores a diseñar una mejor API?
  4. ¿Cómo diseño combinadores eficaces?
  5. ¿A qué se parecen los combinadores en un lenguaje no funcional (digamos, Java), o qué utilizan estos lenguajes en lugar de los combinadores?

Actualizar

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

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

Sospecho que la respuesta es que la versión con mucho 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 combinadores complejos (es decir, más complejos que fold) en lenguajes de programación comunes.

Matt Fenwick
fuente
4
Considero funciones de orden superior map / filter / fold y las uso todo el tiempo. Todavía no tengo idea de qué es un combinador.
1
@pst - Hubiera estado de acuerdo hace 5 días, pero ahora no puedo discutir con John Hughes
Matt Fenwick

Respuestas:

93

No me interesa la primera definición; esas no me ayudarían a escribir un programa real (+1 si me convences de que estoy equivocado). Ayúdame a comprender la segunda definición. Creo que mapear, filtrar y reducir son útiles: me permiten programar en un nivel superior: menos errores, código más corto y claro.

Las dos definiciones son básicamente lo mismo. El primero se basa en la definición formal y los ejemplos que da son combinadores primitivos , los bloques de construcción más pequeños posibles. Pueden ayudarlo a escribir un programa real en la medida en que, con ellos, puede construir combinadores 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, por lo que en la práctica, por lo general, las operaciones de nivel superior se implementarán detrás de escena de otras maneras, pero la base conceptual sigue siendo una herramienta útil para comprender el significado de esas operaciones de nivel superior. 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 formas. 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, hay una distinción 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 una manera general, en lugar de operar en cualquier no funcionan las cosas directamente.

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

¡Demasiados para enumerarlos! Ambos transforman una función que describe el comportamiento de un solo valor en una función que describe el comportamiento de una colección completa. También puede tener funciones que solo transformen otras funciones, como componerlas de un extremo a otro o dividir y recombinar argumentos. Puede tener combinadores que conviertan las operaciones de un solo paso en operaciones recursivas que produzcan o consuman colecciones. O todo tipo de otras cosas, de verdad.

¿Qué combinadores implementan a menudo los lenguajes de programación?

Eso va a variar bastante. Hay relativamente pocos combinadores completamente genéricos, en su mayoría los primitivos mencionados anteriormente, por lo que en la mayoría de los casos, los combinadores tendrán algún conocimiento de las estructuras de datos que se estén utilizando (incluso si esas estructuras de datos se construyen a partir de otros combinadores de todos modos), en las que En el caso de que haya típicamente un puñado de combinadores "totalmente genéricos" y luego cualquier forma especializada que alguien haya decidido proporcionar. Hay una cantidad ridícula de casos en los que (versiones adecuadamente generalizadas de) mapear, plegar y desplegar son suficientes para hacer casi todo lo que pueda desear.

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

Exactamente como dijiste, pensando 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" sobre las colecciones, que le permiten abstraer los detalles de enumerar una colección. Estas son solo operaciones de mapeo / plegado en la mayoría de los casos, y al convertirlo en un combinador (en lugar de sintaxis incorporada) puede hacer cosas como tomar dos bucles existentes y combinarlos directamente de varias maneras: anidar uno dentro del otro, hacer uno tras otro, y así sucesivamente, simplemente aplicando un combinador, en lugar de hacer malabares con un montón de código.

¿Cómo diseño combinadores eficaces?

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

¿A qué se parecen los combinadores en un lenguaje no funcional (digamos, Java), o qué utilizan estos lenguajes en lugar de los combinadores?

Ahahahaha. Es curioso que pregunte, porque los objetos son cosas de orden superior en primer lugar: tienen algunos datos, pero también llevan un montón de operaciones, y mucho de lo que constituye un buen diseño de POO se reduce a "los objetos deberían normalmente actúan como combinadores, no como estructuras de datos ".

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

CA McCann
fuente
¡Gran respuesta! Veamos si lo entiendo: los combinadores no son especiales, sino más bien, ¿una parte integral de la construcción de un sistema de software mantenible? Todavía estoy tratando de digerir la declaración de "fragmentos de programa" de Hughes, en el contexto de su publicación.
Matt Fenwick
@Matt Fenwick: Estoy bastante seguro de que solo está usando "fragmentos de programa" para referirse al tipo de transformaciones / operaciones de las que estoy hablando, particularmente si se trata de "Flechas", que enfatizan ese enfoque aún más fuertemente. Además, no diría que se trata de construir sistemas mantenibles exactamente, más sobre sistemas de construcción que son altamente modulares y están desacoplados de una manera particular , con los beneficios que eso conlleva.
CA McCann
¿Conoce algún buen recurso para leer sobre el uso práctico de los combinadores? ¡Gracias un montón!
Matt Fenwick
@ Matt Fenwick: Lo siento, no tengo nada específico sobre eso. Sin embargo, tiende a ser un enfoque natural para los programas escritos en un estilo muy funcional, por lo que pasar un tiempo con lenguajes que lo alientan fuertemente (por ejemplo, Haskell o Clojure) y observar qué tan limpio e idiomático está escrito en ese lenguaje. , es una buena forma de familiarizarse con el estilo.
CA McCann