La récursivité des régimes pour les nuls?

Question

Je suis à la recherche pour certains c'est vraiment simple, facile à comprendre des explications de la récursivité et de schémas de corecursion régimes (catamorphisms, anamorphisms, hylomorphisms etc.) qui ne nécessitent pas de suite beaucoup de liens, ou de l'ouverture d'une catégorie de la théorie des manuels scolaires. Je suis sûr que j'ai réinventé plusieurs de ces régimes inconsciemment et "appliquée" dans ma tête pendant le processus de codage (je suis sûr que beaucoup d'entre nous l'ont fait), mais je n'ai aucune idée de ce que le (co)récursivité régimes que j'utilise sont appelés. (OK, j'ai menti. Je viens de lire quelques-uns d'entre eux, ce qui a amené à 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 la programmation a été entravée par l'interdiction des explications et des exemples on a tendance à venir à travers, par exemple sur Wikipédia, mais aussi ailleurs.

C'est aussi probablement été entravée par leurs noms. Je pense qu'il y a une alternative, moins mathématique (les noms quelque chose à propos de bananes et de barbelés?) mais je n'ai aucune idée de ce que le cutsier les noms sont pour la récursivité régimes que j'utilise, que ce soit.

Je pense qu'il serait utile d'utiliser des exemples de types de données représentant des simples problèmes du monde réel, plutôt que les types de données abstraites comme des arbres binaires.

Answer 1

Très vaguement parler, une catamorphism est juste une légère généralisation de l' fold, et un anamorphism est une légère généralisation de l' unfold. (Et un hylomorphism est juste un pli du produit de se dérouler.). Ils sont présentés de façon plus rigoureuse forme habituellement, pour établir la connexion à la catégorie théorie plus clair. Le plus dense formulaire vous permet de nous distinguer de données (l'nécessairement fini produit d'un premier algèbre) et codata (éventuellement le produit infini de finale coalgebra). Cette distinction nous permet de garantir qu'un pli n'est jamais appelée sur une liste infinie. L'autre raison pour le drôle de façon que catamorphisms et anamorphisms sont généralement écrit à l'est que par l'exploitation de plus de F-algèbres et F-coalgebras (généré à partir de foncteurs), nous pouvons écrire une fois pour toutes, plutôt que d'une fois sur une liste, une fois de plus un arbre binaire, etc. Cela permet de préciser exactement pourquoi ils sont tous de la même chose.

Mais à partir d'une intuition pure point de vue, vous pouvez penser à cata et ana que la réduction et la production, et c'est à ce sujet.

Edit: un peu plus

Un métamorphisme (Gibbons), c'est comme un hylo-son un se dérouler du produit d'un pli. De sorte que vous pouvez l'utiliser pour abattre un flux de données et de construire une nouvelle avec potentiellement une structure différente.

Ekmett posté un joli "guide de terrain" pour les différents régimes dans la littérature: http://comonad.com/reader/2009/recursion-schemes/

Cependant, alors que le "intuitive" des explications sont simples, liés au code de l'est moins, et les messages de blog sur certaines de ces peut-être un peu sur le complexe/interdiction de côté.

Cela dit, sauf peut-être pour histomorphisms je ne pense pas que le reste du zoo est nécessairement quelque chose que vous voulez penser directement la plupart du temps. Si vous "get" hylo et meta, vous pouvez exprimer presque rien en termes d'eux seuls. Généralement, les autres morphisms sont plus restrictives, pas moins (mais donc vous donner plus de propriétés "gratuitement").

Answer 2

Quelques références, de la plupart de la catégorie de la théorie (mais pertinentes pour donner une "carte du territoire" qui vous permettra d'éviter "en cliquant sur beaucoup de liens") à la plus simple & plus autonome:

• Aussi loin que les "bananes & fil de fer barbelé" vocabulaire va, ça vient de l'original papier de Meijer, Fokkinga & Patterson (et de sa suite, par d'autres auteurs), et c'est en somme tout comme la notation-lourds comme l'est moins mignon alternatives : les "noms" (bananes, etc) sont juste un raccourci de l'apparence graphique de l'ascii notation des constructions qu'ils sont à parité. Par exemple, catamorphisms (c'est à dire des plis) sont représentés avec (| _ |), et le pair-à-parenthèse ressemble à une "banane", d'où le nom. C'est le papier qui est le plus souvent appelé "impénétrable", donc pas la première chose que je regarde si j'étais vous.

• La référence de base pour ceux schémas de récursion (ou plus précisément, pour une approche relationnelle de ces schémas de récursion) est l'Oiseau et de Moor, l' Algèbre de la Programmation (le livre n'est pas disponible, sauf en impression à la demande, mais il y a des copies à la disposition de seconde main et il devrait être dans les bibliothèques). Il contient plus de rythme et une explication détaillée de la programmation gratuite, si elle est encore "académique" : le livre introduit une certaine catégorie de la théorie de vocabulaire, mais de manière autonome. Pourtant, les exercices (que vous ne trouverez pas dans un papier).

• Tri morphisms par la Lex Augustjein, utilise des algorithmes de tri sur les différentes structures de données pour expliquer les schémas de récursion. Il est à peu près "la récursivité des régimes pour les nuls" par construction:

  Cette présentation donne l'occasion de présenter les différents morphisms dans une façon simple, à savoir que des schémas de récursion qui sont utiles dans la programmation fonctionnelle, au lieu de l'approche habituelle via la catégorie de la théorie, qui tend à être inutilement intimidant pour le programmeur moyen.

• Une autre approche pour faire un des symboles-présentation libre est Jeremy Gibbons chapitre Origami de Programmation dans Le Plaisir de la Programmation, avec un certain chevauchement avec la précédente. La bibliographie donne un tour de l'introduction du sujet.

  Edit : Jeremy Gibbons permettez-moi juste de savoir qu'il a ajouté un lien vers la bibliographie de l'ensemble du livre sur le livre de la page web après la lecture de cette question. Profiter de !

J'ai peur que ces deux dernières références uniquement à donner une explication solide de (cata|ana|hylo|para)morphisms, mais mon espoir est que ce serait assez pour déchirer le formalisme algébrique vous pouvez trouver plus de notation-lourds publications. Je ne sais pas du tout strictement non-catégorie de la théorie de l'explication de la (co-)la récursivité des régimes autres que ceux de quatre.

Answer 3

Tim Williams a donné un brillant exposé à Londres Haskell Groupe d'Utilisateurs de la nuit dernière sur la récursivité des mécanismes de motivation exemple de chacune de celles que vous mentionnez. Découvrez les coulisses:

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

Il y a des références à tous les suspects habituels (lentilles, des bananes, du fil de fer barbelé ala carte, etc) à la fin de la glisse et vous pouvez également google "Origami de Programmation", qui est une belle intro que je n'avais pas rencontré avant.

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

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

modifier la Plupart des liens en question sont en huitseeker la réponse ci-dessus.