Czytając ten klasyczny artykuł , utknąłem na paramorfizmach. Niestety sekcja jest dość cienka, a strona Wikipedii nic nie mówi.
Moje tłumaczenie Haskell to:
para :: (a -> [a] -> b -> b) -> b -> [a] -> b
para f base = h
where
h [] = base
h (x:xs) = f x xs (h xs)
Ale nie rozumiem tego - nie mam intuicji co do podpisu typu ani pożądanego rezultatu.
Co to jest paramorfizm i jakie są przydatne przykłady w działaniu?
Tak, widziałem te pytania , ale nie obejmują one bezpośrednio paramorfizmów i wskazują tylko zasoby, które mogą być pomocne jako odniesienia, ale nie jako materiały do nauki.
haskell
recursion
functional-programming
higher-order-functions
Matt Fenwick
źródło
źródło
para f base xs = foldr (uncurry f) base $ zip xs (tail $tails xs)
, wydaje mi się.para f base xs = foldr g base (init $ tails xs) where g (x:xs) = f x xs
. To przypomina Common Lispmaplist
.Odpowiedzi:
Tak, to jest
para
. Porównaj z katamorfizmem lubfoldr
:Niektórzy nazywają paramorfizmy „rekurencją pierwotną” w przeciwieństwie do katamorfizmów (
foldr
) będącymi „iteracjami”.Tam, gdzie
foldr
dwa parametry otrzymują rekursywnie obliczaną wartość dla każdego rekurencyjnego podobiektu danych wejściowych (tutaj jest to koniec listy),para
parametry pobierają zarówno oryginalny podobiekt, jak i wartość obliczoną rekurencyjnie z niego.Przykładową funkcją, która jest ładnie wyrażona za pomocą,
para
jest gromadzenie odpowiednich elementów listy.po to aby
Prawdopodobnie jest jeszcze prostsze
w którym gałąź "przeciw" ignoruje swój rekursywnie obliczany argument i po prostu zwraca ogon. Oceniane leniwie, rekurencyjne obliczenia nigdy się nie zdarzają, a ogon jest wyodrębniany w stałym czasie.
Możesz łatwo zdefiniować
foldr
użyciepara
; to trochę trudniejsze do zdefiniowaniapara
odfoldr
, ale z pewnością jest to możliwe, a każdy powinien wiedzieć, jak to się robi!Sztuczka definiowania za
para
pomocąfoldr
polega na zrekonstruowaniu kopii oryginalnych danych, aby na każdym kroku uzyskać dostęp do kopii ogona, mimo że nie mieliśmy dostępu do oryginału. Na koniecsnd
odrzuca kopię danych wejściowych i podaje tylko wartość wyjściową. Nie jest zbyt wydajna, ale jeśli interesuje Cię czysta ekspresja, niepara
daje więcejfoldr
. Jeśli użyjesz tejfoldr
zakodowanej wersji programupara
, to w końcusafeTail
zajmie to liniowy czas, kopiowanie elementu ogona po elemencie.A więc to wszystko:
para
jest wygodniejszą wersją,foldr
która daje natychmiastowy dostęp do końca listy, jak również do obliczonej z niej wartości.W ogólnym przypadku praca z typem danych wygenerowanym jako rekurencyjny punkt stały funktora
ty masz
i znowu, te dwa są wzajemnie definiowalne, ze
para
zdefiniowanącata
przez tę samą sztuczkę "zrób kopię"Ponownie,
para
nie jest bardziej wyraziste niżcata
, ale wygodniejsze, jeśli potrzebujesz łatwego dostępu do podstruktur wejścia.Edycja: przypomniałem sobie inny fajny przykład.
Rozważ binarne drzewa wyszukiwania według
Fix TreeF
gdziei spróbuj zdefiniować wstawianie dla drzew wyszukiwania binarnego, najpierw jako a
cata
, a następnie jakopara
. Znajdzieszpara
wersji znacznie łatwiejsze, ponieważ w każdym węźle trzeba będzie włożyć w jednym poddrzewie ale zachowanie drugiej, jak to było.źródło