Что такое параморфизмы?

Question

Прочитав эту классическую статью, я застрял на параморфизмах. К сожалению, раздел довольно тонкий, и страница Википедии ничего не говорит.

Мой перевод на Haskell:

para :: (a -> [a] -> b -> b) -> b -> [a] -> b
para f base = h
  where
    h []       =   base
    h (x:xs)   =   f x xs (h xs)

Но я этого не понимаю - у меня нет интуиции для сигнатуры типа или желаемого результата.

Что такое параморфизм и какие полезные примеры в действии?

---

Да, я видел эти вопросы, но они не охватывают параморфизмы напрямую и указывают только на ресурсы, которые могут быть полезны в качестве ссылок, но не в качестве учебных материалов.

Answer 1

Да, это para, Сравните с катаморфизмом или 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

Некоторые люди называют параморфизмы "примитивной рекурсией" в отличие от катаморфизмов (foldr) будучи "итерацией".

куда foldrдва параметра получают рекурсивно вычисленное значение для каждого рекурсивного подобъекта входных данных (здесь это хвост списка), paraПараметры получают как исходный подобъект, так и значение, вычисленное из него рекурсивно.

Пример функции, которая хорошо выражена para это коллекция правильных списков.

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

чтобы

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

Возможно, еще проще

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

в котором ветвь "против" игнорирует свой рекурсивно вычисленный аргумент и просто возвращает хвост. Оцениваемый лениво, рекурсивные вычисления никогда не происходят, и хвост извлекается за постоянное время.

Вы можете определить foldr с помощью para довольно легко; это немного сложнее определить para от foldr, но это, конечно, возможно, и каждый должен знать, как это делается!

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)

Хитрость в определении para с foldr состоит в том, чтобы восстановить копию исходных данных, чтобы мы могли получить доступ к копии хвоста на каждом этапе, даже если у нас не было доступа к оригиналу. В конце, snd отбрасывает копию ввода и дает только выходное значение. Это не очень эффективно, но если вы заинтересованы в явной выразительности, para дает вам не больше, чем foldr, Если вы используете это foldrкодированная версия para, затем safeTail все равно будет занимать линейное время, копируя хвостовой элемент за элементом.

Итак, это все: para это более удобная версия foldr который дает вам немедленный доступ к хвосту списка, а также к значению, вычисленному из него.

В общем случае работа с типом данных, сгенерированным как рекурсивная точка фиксации функтора

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

у тебя есть

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)

и снова, эти два взаимно определим, с para определяется из cata по тому же трюку "сделать копию"

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

Снова, para не более выразителен, чем cata, но удобнее, если вам нужен легкий доступ к подструктурам ввода.

Изменить: я вспомнил еще один хороший пример.

Рассмотрим двоичные деревья поиска, заданные Fix TreeF где

data TreeF sub = Leaf | Node sub Integer sub

и попробуйте определить вставку для двоичных деревьев поиска, сначала как cataтогда как para, Вы найдете para Версия намного проще, так как на каждом узле вам нужно будет вставить в одно поддерево, но сохранить другое, как было.