haskell - sintaxis - recursividad programacion

Esquemas de recursión para dummies?

Question

Estoy buscando explicaciones realmente simples y fáciles de entender de esquemas de recursión y esquemas de corecursion (catamorfismos, anamorphisms, hylomorphisms etc.) que no requieren seguir muchos enlaces, o abrir un libro de texto de teoría de categorías. Estoy seguro de que reinventé muchos de estos esquemas inconscientemente y los "apliqué" en mi cabeza durante el proceso de codificación (estoy seguro de que muchos de nosotros lo hemos hecho), pero no tengo idea de qué esquemas de (co) recursividad uso se llaman. (OK, mentí. Acabo de leer acerca de algunos de ellos, lo que provocó esta pregunta. Pero antes de hoy, no tenía ni idea).

Creo que la difusión de estos conceptos dentro de la comunidad de programación se ha visto obstaculizada por las explicaciones y ejemplos prohibitivos que uno tiende a encontrar, por ejemplo en Wikipedia, pero también en otros lugares.

También es probable que haya sido obstaculizado por sus nombres. Creo que hay algunos nombres alternativos, menos matemáticos (algo sobre plátanos y alambre de púas?) Pero no tengo ni idea de cuáles son los nombres más cortos para los esquemas de recursión que uso, tampoco.

Creo que sería útil usar ejemplos con tipos de datos que representen problemas simples del mundo real, en lugar de tipos de datos abstractos como árboles binarios.

Answer 1

Algunas referencias, desde la mayoría de las categorías teóricas (pero relevantes para dar un "mapa de territorio" que le permitirá evitar "hacer clic en muchos enlaces") para simplificar y más autónomo:

• En cuanto al vocabulario de "plátanos y alambre de púas", esto proviene del artículo original de Meijer, Fokkinga & Patterson (y su secuela de otros autores), y es en resumen tan pesado como la anotación de las alternativas menos lindas: los "nombres" (plátanos, etc.) son solo un atajo para la apariencia gráfica de la notación ascii de las construcciones a las que están vinculados. Por ejemplo, los catamorfismos (es decir, pliegues) se representan con (| _ |) , y el par con paréntesis parece un "plátano", de ahí el nombre. Este es el periódico que con mayor frecuencia se llama "impenetrable", por lo tanto, no es lo primero que buscaría si fuera usted.

• La referencia básica para esos esquemas de recursión (o más precisamente, para un acercamiento relacional a esos esquemas de recursión) es Algebra of Programming de Bird & de Moor''s (el libro no está disponible excepto como impresión bajo demanda, pero hay copias disponibles de segunda mano y debe estar en las bibliotecas). Contiene una explicación más detallada y detallada de la programación sin puntos, si aún es "académica": el libro presenta un vocabulario teórico de categorías, aunque de manera independiente. Sin embargo, los ejercicios (que no encontrarías en un artículo) ayudan.

• Ordenando morfismos por Lex Augustjein , utiliza algoritmos de clasificación en varias estructuras de datos para explicar los esquemas de recursión. Es más o menos " esquemas de recursión para dummies " por construcción:

  Esta presentación ofrece la oportunidad de presentar los diversos morfismos de una manera simple, a saber, como patrones de recursión que son útiles en la programación funcional, en lugar del enfoque habitual a través de la teoría de categorías, que tiende a ser innecesariamente intimidante para el programador promedio.

• Otro enfoque para hacer una presentación libre de símbolos es el capítulo de Jeremy Gibbons Programación de Origami en La diversión de la programación , con cierta superposición con la anterior. Su bibliografía da un recorrido por las introducciones al tema.

  Editar: Jeremy Gibbons solo me deja saber que ha agregado un enlace a la bibliografía de todo el libro en la página web del libro después de leer esta pregunta. ¡ Disfruta !

Me temo que estas dos últimas referencias solo dan una explicación sólida de los morfismos (cata | ana | hylo | para), pero mi esperanza es que esto sea suficiente para romper el formalismo algebraico que se puede encontrar en publicaciones con más notación. No conozco ninguna explicación estrictamente no teórica de categorías de los esquemas de (co) recursividad distintos de esos cuatro.

Answer 2

Tim Williams dio una charla brillante en el London Haskell User Group anoche sobre esquemas de recursión con un ejemplo motivador de cada uno de los que mencionas. Mira las diapositivas:

http://www.timphilipwilliams.com/slides.html

Hay referencias a todos los sospechosos habituales (lentes, plátanos, alambre de púas, carta, etc.) al final de las diapositivas y también puede googlear "Origami Programming", que es una buena introducción que no había visto antes.

y el video estará aquí cuando se cargue:

http://www.youtube.com/user/LondonHaskell

editar La mayoría de los enlaces en cuestión están en la respuesta de huitseeker anterior.

Answer 3

Extremadamente hablando, un catamorfismo es solo una ligera generalización del fold , y un anamorfismo es una ligera generalización del unfold . (Y un hylomorphism es simplemente un despliegue seguido por un doblez). Por lo general, se presentan en una forma más rigurosa para aclarar la conexión con la teoría de categorías. La forma más densa nos permite distinguir datos (el producto necesariamente finito de un álgebra inicial) y codata (el producto posiblemente infinito de una coalgebra final). Esta distinción nos permite garantizar que nunca se invoca un doblez en una lista infinita. La otra razón para la forma divertida en que generalmente se escriben los catamorfismos y anamorfos es que al operar sobre F-álgebras y F-coalgebras (generadas por funtores) podemos escribirlos de una vez por todas, en lugar de una vez sobre una lista, una vez árbol binario, etc. Esto a su vez ayuda a aclarar exactamente por qué son todos la misma cosa.

Pero desde el punto de vista de la intuición pura, puedes pensar en cata y ana como reduciendo y produciendo, y eso es todo.

Editar: un poco más

Un metamorfismo (Gibbons) es como un hylo de adentro hacia afuera, es un doblez seguido de un despliegue. Entonces puede usarlo para derribar una secuencia y crear una nueva con una estructura potencialmente diferente.

Ekmett publicó una buena "guía de campo" para los diversos esquemas en la literatura: http://comonad.com/reader/2009/recursion-schemes/

Sin embargo, si bien las explicaciones "intuitivas" son sencillas, el código vinculado no lo es tanto, y las publicaciones del blog sobre algunas de ellas pueden ser un poco complejas / prohibidas.

Dicho esto, excepto quizás por histomorfismos, no creo que el resto del zoológico sea necesariamente algo con lo que quieras pensar directamente la mayor parte del tiempo. Si "obtienes" hylo y meta, puedes expresar casi cualquier cosa en términos de ellos solos. Típicamente, los otros morfismos son más restrictivos, no menos (pero por lo tanto le dan más propiedades "gratis").