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

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

мой перевод Хаскелл:

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

но я не Грок, что -- у меня нет никакой интуиции для подписи типа или желаемого результата.

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

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

1 90
haskell functional-programming recursion higher-order-functions

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, но более удобно, если вам нужен легкий доступ к подструктурам входа.

Edit: я вспомнил еще один хороший пример.

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

data TreeF sub = Leaf | Node sub Integer sub

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

103