Esquemas de recursão para manequins?

Estou procurando algumas explicações realmente simples e fáceis de entender de esquemas de recursão e esquemas de correcursão (catamorfismos, anamorfismos, hilomorfismos etc.) que não requerem seguir muitos links ou abrir um livro de teoria de categorias. Tenho certeza de que reinventei muitos desses esquemas inconscientemente e os "apliquei" em minha cabeça durante o processo de codificação (tenho certeza que muitos de nós o fizemos), mas não tenho ideia de quais são os esquemas de (co) recursão. uso são chamados. (OK, eu menti. Acabei de ler sobre alguns deles, o que gerou esta pergunta. Mas antes de hoje, eu não tinha ideia.)

Acho que a difusão desses conceitos dentro da comunidade de programação tem sido dificultada pelas explicações e exemplos proibitivos que costumamos encontrar - por exemplo, na Wikipedia, mas também em outros lugares.

Provavelmente também foi prejudicado por seus nomes. Acho que existem alguns nomes alternativos, menos matemáticos (algo sobre bananas e arame farpado?), Mas também não tenho ideia de quais são os nomes mais bonitos para esquemas de recursão que uso.

Acho que ajudaria a usar exemplos com tipos de dados que representam problemas simples do mundo real, em vez de tipos de dados abstratos, como árvores binárias.

Extremamente falando, um catamorfismo é apenas uma ligeira generalização de fold, e um anamorfismo é uma ligeira generalização deunfold. (E um hilomorfismo é apenas um desdobramento seguido por uma dobra.). Geralmente, eles são apresentados de uma forma mais rigorosa, para tornar mais clara a conexão com a teoria das categorias. A forma mais densa nos permite distinguir dados (o produto necessariamente finito de uma álgebra inicial) e codata (o produto possivelmente infinito de uma álgebra final). Essa distinção nos permite garantir que uma dobra nunca seja chamada em uma lista infinita. A outra razão para a forma engraçada como os catamorfismos e anamorfismos são geralmente escritos é que, operando sobre F-álgebras e F-coalgebras (gerados a partir de functores), podemos escrevê-los de uma vez por todas, em vez de apenas uma vez em uma lista, árvore binária etc. Isso, por sua vez, ajuda a deixar claro exatamente por que são todos a mesma coisa.

Mas do ponto de vista da intuição pura, você pode pensar em cata e ana como redutores e produtores, e é isso.

Editar: um pouco mais

Um metamorfismo (Gibbons) é como um hilo de dentro para fora - é uma dobra seguida por um desdobramento. Portanto, você pode usá-lo para derrubar um riacho e construir um novo com uma estrutura potencialmente diferente.

Ekmett postou um bom "guia de campo" para os vários esquemas na literatura: http://comonad.com/reader/2009/recursion-schemes/

No entanto, embora as explicações "intuitivas" sejam diretas, o código vinculado é menos, e as postagens de blog sobre alguns deles podem ser um pouco complexas / proibitivas.

Dito isso, exceto talvez pelos histomorfismos, não acho que o resto do zoológico seja necessariamente algo que você queira pensar diretamente na maior parte do tempo. Se você "obter" hylo e meta, pode expressar quase tudo em termos apenas deles. Normalmente, os outros morfismos são mais restritivos, não menos (mas, portanto, fornecem mais propriedades "de graça").

Algumas referências, desde as mais teóricas de categorias (mas relevantes para dar um "mapa do território" que permitirá que você evite "clicar em muitos links") até as mais simples e independentes:

• No que diz respeito ao vocabulário "bananas e arame farpado", ele vem do artigo original de Meijer, Fokkinga & Patterson (e sua sequência de outros autores) e é, em suma, tão carregado de notações quanto as alternativas menos atraentes: os "nomes" (bananas, etc.) são apenas um atalho para a aparência gráfica da notação ascii das construções às quais estão vinculados. Por exemplo, catamorfismos (ou seja, dobras) são representados com (| _ |), e o par-com-parênteses se parece com uma "banana", daí o nome. Este é o papel mais comumente chamado de "impenetrável", portanto, não é a primeira coisa que eu procuraria se fosse você.

• A referência básica para esses esquemas de recursão (ou mais precisamente, para uma abordagem relacional a esses esquemas de recursão) é Bird & de Moor's Algebra of Programming (o livro não está disponível, exceto como uma impressão sob demanda, mas há cópias disponíveis de segunda mão e deve estar em bibliotecas). Ele contém uma explicação mais rápida e detalhada da programação sem pontos, embora ainda "acadêmica": o livro apresenta algum vocabulário teórico de categorias, embora de uma maneira independente. Ainda assim, os exercícios (que você não encontraria em um papel) ajudam.

• Morfismos de classificação por Lex Augustjein , usa algoritmos de classificação em várias estruturas de dados para explicar esquemas de recursão. É basicamente " esquemas de recursão para manequins " por construção:

  Esta apresentação dá a oportunidade de introduzir os vários morfismos de uma forma simples, nomeadamente como padrões de recursão úteis na programação funcional, em vez da abordagem usual via teoria das categorias, que tende a ser desnecessariamente intimidante para o programador médio.

• Outra abordagem para fazer uma apresentação livre de símbolos é o capítulo Origami Programming de Jeremy Gibbons em The Fun of Programming , com alguma sobreposição com o anterior. Sua bibliografia fornece um tour pelas introduções ao tópico.

  Edit: Jeremy Gibbons, deixe-me saber que ele adicionou um link para a bibliografia de todo o livro na página do livro na web depois de ler esta pergunta. Aproveite !

Temo que essas duas últimas referências apenas dêem uma explicação sólida dos morfismos (cata | ana | hylo | para), mas minha esperança é que isso seja o suficiente para romper o formalismo algébrico que você pode encontrar em publicações com mais notações. Não conheço nenhuma explicação teórica estritamente não categórica de esquemas de (co-) recursão além desses quatro.

Tim Williams deu uma palestra brilhante no London Haskell User Group na noite passada sobre esquemas de recursão com um exemplo motivador de cada um dos que você mencionou. Confira os slides:

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

Há referências a todos os suspeitos usuais (lentes, bananas, arame farpado à la carte etc.) no final dos slides e você também pode pesquisar no Google "Programação de Origami", que é uma boa introdução que eu não tinha visto antes.

e o vídeo estará aqui quando for carregado:

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

editar A maioria dos links em questão estão na resposta do huitseeker acima.