Czym są paramorfizmy?

Question

Czym 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 Haskella 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 ja tego nie rozumiem -- nie mam żadnej intuicji co do podpisu typu czy pożądanego rezultatu.

Co to jest paramorfizm i jakie są przydatne przykłady w działaniu?

Tak, widziałem Te Pytania, ale nie obejmują paramorfizmy bezpośrednio i tylko wskazują na zasoby , które mogą być pomocne jako odniesienia, ale nie jako materiały do nauki.

90

haskell functional-programming recursion higher-order-functions

Author: Community, 2012-11-10

Source

1 answers

score 103 · Accepted Answer

Tak, to 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 "prymitywną rekurencją", w przeciwieństwie do katamorfizmów (foldr) będących "iteracją".

Gdzie foldr dwa parametry otrzymują rekurencyjnie obliczoną wartość dla każdego rekurencyjnego podobiektu danych wejściowych (tutaj jest to ogon listy), para parametry pobierają zarówno oryginalny podobiekt, jak i wartość obliczaną rekurencyjnie z niego.

Przykładowa funkcja, która jest ładnie wyrażona za pomocą {[9] } jest zbiorem odpowiednich sufiksów listy.

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

Tak, że

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

Prawdopodobnie prostsze jest jeszcze

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

W którym gałąź "cons" ignoruje rekurencyjnie obliczony argument i po prostu oddaje ogon. Obliczanie rekurencyjne nigdy się nie zdarza, a ogon jest wydobywany w stałym czasie.

Możesz zdefiniować foldr używając para dość łatwo; trochę trudniej jest zdefiniować para z foldr, ale to z pewnością możliwe i 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 do zdefiniowania para za pomocą foldrpolega na zrekonstruowaniu kopii oryginalnych danych, tak aby uzyskać dostęp do kopii ogona na każdym kroku, nawet jeśli nie mieliśmy dostępu do oryginału. Na końcu snd odrzuca kopię danych wejściowych i podaje tylko wartość wyjściową. Nie jest zbyt wydajny, ale jeśli interesuje Cię czysta ekspresja, para daje nie więcej niż foldr. Jeśli używasz tego foldr - zakodowana wersja para, wtedy safeTail zajmie liniowy czas, kopiowanie elementu ogonowego po elemencie.

To jest to: para jest wygodniejszą wersją foldr, która daje natychmiastowy dostęp do ogona listy, jak również wartości obliczonej z niej.

W tym przypadku, praca z typem danych generowanym jako rekurencyjny punkt fixpoint functora {[38]]}

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

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, z para w tym celu należy wykonać kopię zapasową, a następnie wykonać kopię zapasową.]}

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

Ponownie, para nie jest bardziej wyrazisty niż cata, ale wygodniejszy, jeśli potrzebujesz łatwego dostępu do podstruktur wejścia.

Edit: przypomniałem sobie inny ładny przykład.

Rozważmy binarne drzewa wyszukiwania podane przez Fix TreeF gdzie

data TreeF sub = Leaf | Node sub Integer sub

I spróbuj zdefiniować wstawianie dla binarnych drzew wyszukiwania, najpierw jako cata, a następnie jako para. Wersja para będzie znacznie łatwiejsza, ponieważ w każdym węźle będzie musiał wstawić w jednym poddrzewie, ale zachować drugi tak, jak to było.