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.
źródło
Odpowiedzi:
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”).
źródło
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 ”:
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.
źródło
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.
źródło