Co to są paramorfizmy?

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.

Tak, to jest para. Porównaj z katamorfizmem lub foldr:

para  :: (a -> [a] -> b -> b) -> b -> [a] -> b
foldr :: (a ->        b -> b) -> b -> [a] -> b

para  c n (x : xs) = c x xs (para c n xs)
foldr c n (x : xs) = c x    (foldr c n xs)
para  c n []       = n
foldr c n []       = n

Niektórzy nazywają paramorfizmy „rekurencją pierwotną” w przeciwieństwie do katamorfizmów ( foldr) będącymi „iteracjami”.

Tam, gdzie foldrdwa parametry otrzymują rekursywnie obliczaną wartość dla każdego rekurencyjnego podobiektu danych wejściowych (tutaj jest to koniec listy), paraparametry pobierają zarówno oryginalny podobiekt, jak i wartość obliczoną rekurencyjnie z niego.

Przykładową funkcją, która jest ładnie wyrażona za pomocą, parajest gromadzenie odpowiednich elementów listy.

suff :: [x] -> [[x]]
suff = para (\ x xs suffxs -> xs : suffxs) []

po to aby

suff "suffix" = ["uffix", "ffix", "fix", "ix", "x", ""]

Prawdopodobnie jest jeszcze prostsze

safeTail :: [x] -> Maybe [x]
safeTail = para (\ _ xs _ -> Just xs) Nothing

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ć foldrużycie para; to trochę trudniejsze do zdefiniowania paraod foldr, ale z pewnością jest to możliwe, a każdy powinien wiedzieć, jak to się robi!

foldr c n =       para  (\ x  xs  t ->           c x    t)       n
para  c n = snd . foldr (\ x (xs, t) -> (x : xs, c x xs t)) ([], n)

Sztuczka definiowania za parapomocą foldrpolega 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 koniec sndodrzuca kopię danych wejściowych i podaje tylko wartość wyjściową. Nie jest zbyt wydajna, ale jeśli interesuje Cię czysta ekspresja, nie paradaje więcej foldr. Jeśli użyjesz tej foldrzakodowanej wersji programu para, to w końcu safeTailzajmie to liniowy czas, kopiowanie elementu ogona po elemencie.

A więc to wszystko: parajest wygodniejszą wersją, foldrktó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

data Fix f = In (f (Fix f))

ty masz

cata :: Functor f => (f         t  -> t) -> Fix f -> t
para :: Functor f => (f (Fix f, t) -> t) -> Fix f -> t

cata phi (In ff) = phi (fmap (cata phi) ff)
para psi (In ff) = psi (fmap keepCopy   ff) where
  keepCopy x = (x, para psi x)

i znowu, te dwa są wzajemnie definiowalne, ze parazdefiniowaną cataprzez tę samą sztuczkę "zrób kopię"

para psi = snd . cata (\ fxt -> (In (fmap fst fxt), psi fxt))

Ponownie, paranie 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 TreeFgdzie

data TreeF sub = Leaf | Node sub Integer sub

i spróbuj zdefiniować wstawianie dla drzew wyszukiwania binarnego, najpierw jako a cata, a następnie jako para. Znajdziesz parawersji znacznie łatwiejsze, ponieważ w każdym węźle trzeba będzie włożyć w jednym poddrzewie ale zachowanie drugiej, jak to było.