Frage Rekursionschemata für Dummies?


Ich suche nach wirklich einfachen, leicht zu erfassenden Erklärungen von Rekursionsschemata und Co-Rekursionsschemata (Katamorphismen, Anamorphismen, Hylomorphismen etc.), die nicht viele Links enthalten müssen oder ein Kategorientheorie-Lehrbuch öffnen. Ich bin mir sicher, dass ich viele dieser Schemata unbewusst neu erfunden habe und sie während des Codierens in meinem Kopf "angewendet" habe (ich bin sicher, dass viele von uns es haben), aber ich habe keine Ahnung, was die (Co-) Rekursionsschemata sind Verwendung genannt werden. (OK, ich habe gelogen. Ich habe gerade über ein paar von ihnen gelesen, was diese Frage ausgelöst hat. Aber vor heute hatte ich keine Ahnung.)

Ich denke, dass die Verbreitung dieser Konzepte innerhalb der Programmiergemeinschaft durch die verbietenden Erklärungen und Beispiele behindert wurde, auf die man oft stößt - zum Beispiel auf Wikipedia, aber auch anderswo.

Es ist wahrscheinlich auch durch ihre Namen behindert worden. Ich denke, es gibt einige alternative, weniger mathematische Namen (etwas über Bananen und Stacheldraht?), Aber ich habe keine Ahnung, was die kürzeren Namen für Rekursionssysteme sind, die ich auch verwende.

Ich denke, es wäre hilfreich, Beispiele mit Datentypen zu verwenden, die einfache reale Probleme darstellen, und keine abstrakten Datentypen wie Binärbäume.


76
2017-08-04 13:03


Ursprung


Antworten:


Äußerst locker ist ein Katamorphismus nur eine leichte Verallgemeinerung von foldund ein Anamorphismus ist eine leichte Verallgemeinerung von unfold. (Und ein Hylomorphismus ist nur eine Entfaltung, gefolgt von einer Falte.). Sie werden üblicherweise in einer strengeren Form dargestellt, um die Verbindung zur Kategorientheorie klarer zu machen. Die dichtere Form lässt uns Daten (das notwendigerweise endliche Produkt einer anfänglichen Algebra) und Codata (das möglicherweise unendliche Produkt eines abschließenden cohlegebra) unterscheiden. Mit dieser Unterscheidung können wir garantieren, dass eine Faltung niemals auf einer unendlichen Liste aufgerufen wird. Der andere Grund für die komische Art, wie Katamorphismen und Anamorphismen allgemein geschrieben werden, ist, dass wir, wenn wir über F-Algebren und F-Koalgebren (erzeugt von Funktoren) arbeiten, sie für immer und nicht nur einmal über eine Liste schreiben können Binärbaum usw. Dies wiederum hilft genau zu verdeutlichen Warum sie sind alle gleich.

Aber von einem reinen Intuitionsstandpunkt aus kann man an Kata und Ana denken, als reduzierend und produzierend, und das ist es auch.

Edit: ein bisschen mehr

Eine Metamorphose (Gibbons) ist wie eine von innen nach außen verlaufende Hylo-Form - eine Falte, gefolgt von einer Entfaltung. Sie können damit einen Strom abreißen und einen neuen mit einer möglicherweise anderen Struktur aufbauen.

Ekmett hat einen schönen "Feldführer" zu den verschiedenen Schemata in der Literatur geschrieben: http://comonad.com/reader/2009/recursion-schemes/

Während die "intuitiven" Erklärungen einfach sind, ist der verknüpfte Code jedoch weniger, und die Blog-Posts auf einigen davon könnten ein bisschen auf der komplexen / abweisenden Seite sein.

Abgesehen von Histomorphismen glaube ich nicht, dass der Rest des Zoos notwendigerweise etwas ist, mit dem man die meiste Zeit direkt denken möchte. Wenn Sie hylo und meta "bekommen", können Sie fast alles in Bezug auf sie allein ausdrücken. Typischerweise sind die anderen Morphismen restriktiver, nicht weniger (geben Ihnen aber mehr Eigenschaften "kostenlos").


39
2017-08-04 15:06



Ein paar Referenzen, von den meisten kategorientheoretischen (aber relevant, um eine "Gebietskarte" zu geben, die Sie vermeidet, "viele Links zu klicken"), um die einfachere und in sich geschlossene:

  • Soweit das Wort "Bananen & Stacheldraht" reicht, kommt dies von das Originalpapier von Meijer, Fokkinga & Patterson (und seine Fortsetzung von anderen Autoren), und es ist in der Summe genauso Notation-schwer wie die weniger süßen Alternativen: die "Namen" (Bananen, etc.) sind nur eine Abkürzung für die grafische Darstellung der Ascii-Notation der Konstruktionen sie sind an gebunden. Zum Beispiel werden Katamorphismen (d. H. Falten) mit dargestellt (| _ |)und die Par-with-Parenthesis sieht wie eine "Banane" aus, daher der Name. Dies ist das Papier, das am häufigsten als "undurchdringlich" bezeichnet wird, also nicht das erste, was ich nachschlagen würde, wenn ich du wäre.

  • Die grundlegende Referenz für diese Rekursionssysteme (oder genauer gesagt, für einen relationalen Ansatz zu diesen Rekursionssystemen) ist Bird & de Moor's Algebra der Programmierung (Das Buch ist nicht verfügbar, außer als Print-on-Demand, aber es gibt Kopien, die aus zweiter Hand verfügbar sind und in Bibliotheken vorhanden sein sollten). Es enthält eine ausführlichere und detailliertere Erklärung der punktfreien Programmierung, wenn sie noch "akademisch" ist: das Buch führt ein kategorientheoretisches Vokabular ein, allerdings in einer selbständigen Art und Weise. Doch helfen die Übungen (die Sie nicht in einer Zeitung finden würden).

  • Morphismen sortieren von Lex Augustjein, verwendet Sortieralgorithmen für verschiedene Datenstrukturen, um Rekursionschemata zu erklären. Es ist ziemlich viel "Rekursionsschemata für Dummies" Durch den Bau:

    Diese Präsentation bietet die Möglichkeit, die verschiedenen Morphismen in   ein einfacher Weg, nämlich als Muster der Rekursion, die in der funktionalen Programmierung nützlich sind, anstelle des üblichen Ansatzes über die Kategorientheorie, der für den durchschnittlichen Programmierer unnötig unnötig einschüchternd ist.

  • Ein weiterer Ansatz für eine symbolfreie Präsentation ist Jeremy Gibbons 'Kapitel Origami Programmierung im Der Spaß am Programmieren, mit einigen Überschneidungen mit dem vorherigen. Die Bibliographie gibt einen Überblick über die Einführungen in das Thema.

    Bearbeiten: Jeremy Gibbons Lass mich einfach wissen, dass er einen Link zu der Bibliographie des ganzen Buches über die. hinzugefügt hat Buchseite nach dem Lesen dieser Frage. Genießen !

Ich fürchte, diese letzten beiden Referenzen geben nur eine solide Erklärung für (cata | ana | hylo | para) -Morphismen, aber meine Hoffnung ist, dass dies ausreichen würde, um den algebraischen Formalismus zu durchbrechen, den Sie in mehr notationslastigen Publikationen finden können. Ich kenne keine streng kategorientheoretische Erklärung anderer (Co-) Rekursionssysteme als diese vier.


22
2017-08-05 23:28



Tim Williams hat gestern Abend in der Londoner Haskell User Group einen brillanten Vortrag über Rekursionssysteme gehalten, mit einem motivierenden Beispiel für jeden der von Ihnen erwähnten. Sieh dir die Folien an:

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

Es gibt Verweise auf alle üblichen Verdächtigen (Objektive, Bananen, Stacheldraht Ala Carte etc.) am Ende der Folien und Sie könnten auch googeln "Origami Programming", das ist ein nettes Intro, das ich noch nie zuvor gesehen hatte.

und das Video wird hier sein, wenn es hochgeladen wird:

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

bearbeiten Die meisten der in Frage stehenden Verbindungen sind in der Antwort von hitseeker oben.


15
2018-03-28 16:56