Читая эту классическую статью , я зацикливаюсь на параморфизмах. К сожалению, раздел довольно тонкий, и на странице Википедии ничего не сказано.
Мой перевод на Haskell:
para :: (a -> [a] -> b -> b) -> b -> [a] -> b
para f base = h
where
h [] = base
h (x:xs) = f x xs (h xs)
Но меня это не волнует - у меня нет интуиции относительно сигнатуры типа или желаемого результата.
Что такое параморфизм и какие полезные примеры в действии?
Да, я видел эти вопросы , но они не охватывают напрямую параморфизмы и указывают только на ресурсы, которые могут быть полезны в качестве справочных материалов, но не в качестве учебных материалов.
para f base xs = foldr (uncurry f) base $ zip xs (tail $tails xs)
, мне кажется.para f base xs = foldr g base (init $ tails xs) where g (x:xs) = f x xs
. Это напоминает Common Lispmaplist
.Ответы:
Да вот
para
. Сравните с катаморфизмом, илиfoldr
:Некоторые люди называют параморфизмы «примитивной рекурсией», в отличие от катаморфизмов (
foldr
), являющихся «итерацией».Если
foldr
двум параметрам присваивается рекурсивно вычисляемое значение для каждого рекурсивного подобъекта входных данных (здесь это конец списка), тоpara
параметры получают как исходный подобъект, так и значение, рекурсивно вычисленное из него.Пример функции, которая хорошо выражена,
para
- это сбор необходимых элементов списка.так что
Возможно, еще проще
в котором ветвь cons игнорирует свой рекурсивно вычисляемый аргумент и просто возвращает хвост. При ленивой оценке рекурсивное вычисление никогда не происходит, а хвост извлекается за постоянное время.
Вы можете довольно легко определить
foldr
usingpara
; это немного сложнее определитьpara
сfoldr
, но это, конечно , возможно, и каждый должен знать , как это делается!Уловка для определения
para
с помощьюfoldr
состоит в том, чтобы восстановить копию исходных данных, чтобы мы получали доступ к копии хвоста на каждом шаге, даже если у нас не было доступа к оригиналу. В концеsnd
отбрасывает копию ввода и дает только выходное значение. Это не очень эффективно, но, если вас интересует чистая выразительность,para
не более чемfoldr
. Если вы используете этуfoldr
закодированную версиюpara
, то вsafeTail
конце концов, копирование хвоста элемент за элементом займет линейное время.Итак, вот и все:
para
это более удобная версия,foldr
которая дает вам немедленный доступ к хвосту списка, а также к вычисленному из него значению.В общем случае работа с типом данных, созданным как рекурсивная фиксированная точка функтора
у тебя есть
и, опять же, эти два понятия являются взаимно определяемыми, что
para
определяетсяcata
одним и тем же трюком "сделать копию"Опять же,
para
это не более выразительноcata
, но более удобно, если вам нужен легкий доступ к подструктурам ввода.Изменить: я вспомнил еще один хороший пример.
Рассмотрим деревья двоичного поиска, заданные как
Fix TreeF
гдеи попробуйте определить вставку для двоичных деревьев поиска сначала как
cata
, затем какpara
. Вы найдетеpara
версию намного проще, поскольку на каждом узле вам нужно будет вставить одно поддерево, но сохранить другое, как было.источник