Schematy rekurencyjne dla manekinów?

Szukam naprawdę prostych, łatwych do zrozumienia wyjaśnień schematów rekurencyjnych i korekturalnych (katamorfizmów, anamorfizmów, hylomorfizmów itp.), Które nie wymagają podążania za wieloma linkami ani otwierania podręcznika teorii kategorii. Jestem pewien, że wymyśliłem wiele z tych schematów nieświadomie i "zastosowałem" je w swojej głowie podczas procesu kodowania (jestem pewien, że wielu z nas ma), ale nie mam pojęcia, jakie schematy (ko) rekurencji. używać. (OK, skłamałem. Właśnie przeczytałem o kilku z nich, co wywołało to pytanie. Ale do dzisiaj nie miałem pojęcia.)

Myślę, że rozpowszechnianie tych koncepcji w społeczności programistów zostało utrudnione przez zaborcze wyjaśnienia i przykłady, które można spotkać - na przykład na Wikipedii, ale także gdzie indziej.

Prawdopodobnie utrudniają to również ich nazwy. Myślę, że istnieją alternatywne, mniej matematyczne nazwy (coś o bananach i drutach kolczastych?), Ale nie mam pojęcia, jakie są bardziej trafne nazwy schematów rekurencji, których używam.

Myślę, że pomocne byłoby użycie przykładów z typami danych reprezentującymi proste problemy świata rzeczywistego, zamiast abstrakcyjnych typów danych, takich jak drzewa binarne.

Bardzo luźno mówiąc, katamorfizm jest tylko niewielkim uogólnieniem fold, a anamorfizm jest niewielkim uogólnieniemunfold. (A hylomorfizm to po prostu rozwinięcie, po którym następuje fałd). Zazwyczaj są one przedstawiane w bardziej rygorystycznej formie, aby wyraźniejszy był związek z teorią kategorii. Gęstsza forma pozwala nam rozróżnić dane (koniecznie skończony iloczyn początkowej algebry) i kodata (możliwie nieskończony iloczyn koalgebry). To rozróżnienie pozwala nam zagwarantować, że fałda nigdy nie zostanie wywołana na nieskończonej liście. Innym powodem zabawnego sposobu, w jaki ogólnie pisze się katamorfizmy i anamorfizmy, jest to, że operując na F-algebrach i F-koalgebrach (generowanych przez funktory), możemy je zapisać raz na zawsze, a nie raz na liście, raz na drzewo binarne itp. To z kolei pomaga wyjaśnić dokładnie, dlaczego wszystkie są tym samym.

Ale z czysto intuicyjnego punktu widzenia, możesz myśleć o kata i ana jako o redukcji i wytwarzaniu, i to wszystko.

Edycja: trochę więcej

Metamorfizm (Gibbons) jest jak hylo na lewą stronę - to fałd, po którym następuje rozwinięcie. Możesz więc użyć go do zerwania strumienia i zbudowania nowego o potencjalnie innej strukturze.

Ekmett opublikował ładny „przewodnik terenowy” po różnych schematach w literaturze: http://comonad.com/reader/2009/recursion-schemes/

Jednak podczas gdy „intuicyjne” wyjaśnienia są proste, linkowany kod jest mniejszy, a posty na blogu na niektórych z nich mogą być odrobinę skomplikowane / odstręczające.

To powiedziawszy, z wyjątkiem być może histomorfizmów, nie sądzę, aby reszta zoo była koniecznie czymś, o czym chciałbyś myśleć bezpośrednio przez większość czasu. Jeśli "dostaniesz" hylo i meta, możesz wyrazić prawie wszystko za pomocą samych tylko nich. Zazwyczaj inne morfizmy są bardziej restrykcyjne, a nie mniejsze (ale w związku z tym dają więcej właściwości „za darmo”).

Kilka odniesień, od najbardziej teoretycznych dla kategorii (ale mających znaczenie dla stworzenia „mapy terytorium”, która pozwoli Ci uniknąć „klikania wielu linków”) do prostszych i bardziej samodzielnych:

• Jeśli chodzi o słownictwo „banany i drut kolczasty”, pochodzi ono z oryginalnego artykułu Meijera, Fokkinga i Pattersona (oraz jego kontynuacji innych autorów) i jest w sumie tak samo ciężkie jak mniej urocze alternatywy: "nazwy" (banany, itp.) to tylko skrót do graficznego wyglądu notacji ascii konstrukcji, do których są przymocowane. Na przykład katamorfizmy (tj. Fałdy) są reprezentowane przez (| _ |), a par-z-nawiasami wygląda jak „banan”, stąd nazwa. To jest dokument, który jest najczęściej nazywany „nieprzeniknionym”, więc nie jest pierwszą rzeczą, na którą spojrzałbym na twoim miejscu.

• Podstawowym odniesieniem dla tych schematów rekursji (a dokładniej, dla relacyjnego podejścia do tych schematów rekursji) jest Algebra programowania Bird & de Moor (książka jest niedostępna, z wyjątkiem wersji drukowanej na żądanie, ale są dostępne kopie z drugiej ręki i powinno być w bibliotekach). Zawiera bardziej dynamiczne i szczegółowe wyjaśnienie programowania bez punktów, choć nadal „akademickie”: książka wprowadza pewne słownictwo z teorii kategorii, choć w sposób niezależny. Jednak ćwiczenia (których nie znajdziesz w artykule) pomagają.

• Sorting morphism by Lex Augustjein , używa algorytmów sortowania na różnych strukturach danych do wyjaśnienia schematów rekursji. Z założenia jest to „ schematy rekurencji dla manekinów ”:

  Prezentacja ta daje możliwość przedstawienia różnych morfizmów w prosty sposób, mianowicie jako wzorce rekursji przydatne w programowaniu funkcjonalnym, zamiast zwykłego podejścia za pomocą teorii kategorii, co jest niepotrzebnie onieśmielające dla przeciętnego programisty.

• Innym podejściem do tworzenia prezentacji bez symboli jest rozdział Origami Programming Jeremy'ego Gibbonsa w The Fun of Programming , który częściowo pokrywa się z poprzednim. Jego bibliografia zawiera wprowadzenie do tematu.

  Edycja: Jeremy Gibbons tylko dał mi znać, że po przeczytaniu tego pytania dodał link do bibliografii całej książki na stronie internetowej książki. Ciesz się !

Obawiam się, że te dwie ostatnie wzmianki dają tylko solidne wyjaśnienie morfizmów (cata | ana | hylo | para), ale mam nadzieję, że wystarczyłoby to do przedarcia się przez algebraiczny formalizm, który można znaleźć w publikacjach o większej liczbie notacji. Nie znam żadnego innego niż te cztery wyjaśnienia schematów (ko) rekurencji, które nie byłyby ściśle kategoriami.

Tim Williams wygłosił wczoraj w London Haskell User Group błyskotliwą prelekcję na temat schematów rekurencji, przedstawiając motywujący przykład każdego z wymienionych przez Ciebie. Sprawdź slajdy:

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

Na końcu slajdów znajdują się odniesienia do wszystkich zwykłych podejrzanych (soczewki, banany, drut kolczasty ala carte itp.), A także można wygooglować w Google „Programowanie origami”, które jest miłym wstępem, na które wcześniej nie trafiłem.

a film będzie tutaj po przesłaniu:

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

edytuj Większość odnośników znajduje się w odpowiedzi na pytanie powyżej.