Schémas de récursivité pour les nuls?

Je cherche des explications très simples et faciles à comprendre sur les schémas de récurrence et les schémas de corécession (catamorphismes, anamorphismes, hylomorphismes, etc.) qui n’exigent pas beaucoup de liens ou ouvrent un manuel de théorie des catégories. Je suis sûr que j’ai réinventé beaucoup de ces systèmes inconsciemment et les ai “appliqués” dans ma tête pendant le processus de codage (j’en suis sûr que beaucoup d’entre nous), mais je n’ai aucune idée de ce que les utiliser sont appelés. (OK, j’ai menti. Je viens d’en lire quelques-unes, ce qui a suscité cette question. Mais avant aujourd’hui, je n’avais aucune idée.)

Je pense que la diffusion de ces concepts au sein de la communauté de programmation a été entravée par les explications et les exemples interdits que l’on a tendance à rencontrer, par exemple sur Wikipedia, mais aussi ailleurs.

Ils ont probablement aussi été gênés par leurs noms. Je pense qu’il y a d’autres noms moins mathématiques (quelque chose sur les bananes et les barbelés?) Mais je ne sais pas non plus quels sont les noms plus simples pour les schémas de récurrence que j’utilise non plus.

Je pense qu’il serait utile d’utiliser des exemples avec des types de données représentant des problèmes simples du monde réel, plutôt que des types de données abstraits tels que les arbres binarys.

De manière extrêmement vague, un catamorphisme n’est qu’une légère généralisation du fold et un anamorphisme est une légère généralisation du unfold . (Et un hylomorphisme est juste un déploiement suivi d’un pli.). Ils sont présentés sous une forme plus rigoureuse, pour rendre plus claire la connexion à la théorie des catégories. La forme la plus dense permet de distinguer les données (le produit nécessairement fini d’une algèbre initiale) et les codata (le produit éventuellement infini d’une coalgebra finale). Cette distinction nous permet de garantir qu’un pli n’est jamais appelé sur une liste infinie. L’autre raison de la façon amusante dont les catamorphismes et les anamorphismes s’écrivent est qu’en opérant sur des algèbres F et des hublots de charbon (générés à partir de foncteurs), nous pouvons les écrire une fois pour toutes plutôt qu’une fois sur une liste. arbre binary, etc. Cela aide à clarifier exactement pourquoi ils sont tous la même chose.

Mais du sharepoint vue de l’intuition pure, vous pouvez penser que cata et ana se réduisent et produisent, et c’est à peu près tout.

Edit: un peu plus

Un métamorphisme (Gibbons) est comme un hylo à l’envers – c’est un pli suivi d’un déploiement. Vous pouvez donc l’utiliser pour détruire un stream et en créer un nouveau avec une structure potentiellement différente.

Ekmett a publié un joli “guide de terrain” sur les différents schémas de la littérature: http://comonad.com/reader/2009/recursion-schemes/

Cependant, alors que les explications “intuitives” sont simples, le code lié l’est moins, et les articles de blog sur certains d’entre eux peuvent être un peu complexes / interdits.

Cela dit, sauf peut-être pour les histomorphismes, je ne pense pas que le rest du zoo est nécessairement quelque chose que vous voudriez penser directement la plupart du temps. Si vous “obtenez” hylo et meta, vous pouvez exprimer à peu près n’importe quoi en termes de ces seuls. Typiquement, les autres morphismes sont plus ressortingctifs, pas moins (mais vous donnent donc plus de propriétés “gratuitement”).

Quelques références, parmi les plus théoriques de la catégorie (mais pertinentes pour donner une “carte du territoire” qui vous évitera de “cliquer sur un tas de liens”) vers le plus simple et le plus autonome:

  • En ce qui concerne le vocabulaire “bananes et barbelés”, cela vient du papier original de Meijer, Fokkinga & Patterson (et sa suite par d’autres auteurs), et il est en sum aussi lourd de notation que les alternatives moins mignonnes: les “noms” (bananes, etc.) ne sont qu’un raccourci vers l’aspect graphique de la notation ascii des constructions auxquelles ils sont rattachés. Par exemple, les catamorphismes (c.-à-d. Les plis) sont représentés avec (| _ |) , et le par-avec-parenthèse ressemble à une “banane”, d’où le nom. C’est le journal le plus souvent appelé “impénétrable”, donc pas la première chose que je rechercherais si j’étais toi.

  • La référence de base pour ces schémas de récursivité (ou plus précisément pour une approche relationnelle de ces schémas de récursivité) est l’ Algèbre de programmation de Bird & de Moor (le livre n’est disponible qu’à la demande d’impression, mais il existe des copies de seconde main). & il devrait être dans les bibliothèques). Elle contient une explication plus rythmée et détaillée de la programmation sans points, même si elle est encore «académique»: le livre introduit un vocabulaire de théorie des catégories, mais de manière autonome. Pourtant, les exercices (que vous ne trouverez pas dans un document) aident.

  • Le sorting des morphismes par Lex Augustjein utilise des algorithmes de sorting sur différentes structures de données pour expliquer les schémas de récursivité. Il s’agit plutôt de ” schémas de récursivité pour les nuls ” par construction:

    Cette présentation donne l’occasion d’introduire les différents morphismes de façon simple, à savoir des modèles de récursivité utiles dans la functional programming, au lieu de l’approche habituelle par la théorie des catégories, qui tend à être intimidante pour le programmeur moyen.

  • Le chapitre Origami Programming in The Fun of Programming de Jeremy Gibbons , avec quelques recoupements avec le précédent, constitue une autre approche pour faire une présentation sans symboles. Sa bibliographie fait le tour des introductions au sujet.

    Edit: Jeremy Gibbons vient de me faire savoir qu’il a ajouté un lien vers la bibliographie du livre entier sur la page Web du livre après avoir lu cette question. Profitez-en !

Je crains que ces deux dernières références ne donnent qu’une explication solide des morphismes (cata | ana | hylo | para), mais j’espère que cela suffira à déchirer le formalisme algébrique que vous pouvez trouver dans des publications comportant beaucoup plus de notation. Je ne connais aucune explication ssortingctement non théorique des schémas de (co) récurrence autres que ces quatre.

Tim Williams a donné une shinye présentation hier soir au London Haskell User Group sur les schémas de récursivité avec un exemple motivant de chacun de ceux que vous mentionnez. Découvrez les diapositives:

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

Il y a des références à tous les suspects habituels (lentilles, bananes, barbelés à la carte, etc.) à la fin des diapositives et vous pouvez aussi aller sur Google “Origami Programming”, une belle intro que je n’avais jamais rencontrée auparavant.

et la vidéo sera là quand il sera téléchargé:

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

edit La plupart des liens en question sont dans la réponse de huitseeker ci-dessus.