Анаморфизм
В компьютерном программировании анаморфизм — это функция, которая генерирует последовательность путем многократного применения функции к ее предыдущему результату. Вы начинаете с некоторого значения A и применяете к нему функцию f, чтобы получить B. Затем вы применяете f к B, чтобы получить C, и так далее, пока не будет достигнуто какое-то завершающее условие. Анаморфизм — это функция, которая генерирует список A, B, C и т. д. Вы можете думать об анаморфизме как о развертывании исходного значения в последовательность.
Приведенное выше описание непрофессионала можно сформулировать более формально в теории категорий анаморфизм коиндуктивного типа означает присвоение коалгебры ее уникальному морфизму конечной коалгебре эндофунктора : . Эти объекты используются в функциональном программировании по мере развертывания .
Категориальным двойственным (то есть противоположным) анаморфизму является катаморфизм .
Анаморфизмы в функциональном программировании
[ редактировать ]В функциональном программировании анаморфизм списков обобщением концепции развертки коиндуктивных является . Формально анаморфизмы — это общие функции , которые могут коркурсивно создавать результат определенного типа и параметризуются функциями, определяющими следующий шаг построения.
Рассматриваемый тип данных определяется как наибольшая фиксированная точка ν X . FX функтора F . По универсальному свойству финальных коалгебр существует единственный морфизм коалгебр A → ν X . FX для любой другой F -коалгебры a: A → FA . Таким образом, можно определить функции из типа A _в_ коиндуктивный тип данных, указав структуру коалгебры a на A .
Пример: потенциально бесконечные списки
[ редактировать ]В качестве примера тип потенциально бесконечных списков (с элементами фиксированного типа value ) задан как фиксированная точка [value] = ν X. value × X + 1 , т.е. список состоит либо из значения и последующего списка, либо он пуст. (Псевдо-) Haskell -Определение может выглядеть так:
data [value] = (value:[value]) | []
Это фиксированная точка функтора F value
, где:
data Maybe a = Just a | Nothing
data F value x = Maybe (value, x)
Легко проверить, что действительно тип [value]
изоморфен F value [value]
, и таким образом [value]
является фиксированной точкой.
(Также обратите внимание, что в Haskell наименьшая и наибольшая неподвижные точки функторов совпадают, поэтому индуктивные списки — это то же самое, что и коиндуктивные, потенциально бесконечные списки.)
Анаморфизм . для списков (тогда обычно известный как unfold ) создавал бы (потенциально бесконечный) список на основе значения состояния Обычно развертывание принимает значение состояния x
и функция f
который дает либо пару значения и нового состояния, либо одиночный элемент, обозначающий конец списка. Затем анаморфизм начинается с первого начального числа, вычисляется, продолжается ли список или заканчивается, и в случае непустого списка добавляется вычисленное значение к рекурсивному вызову анаморфизма.
Определение развертки в Haskell или анаморфизма для списков, называемое ana
, заключается в следующем:
ana :: (state -> Maybe (value, state)) -> state -> [value]
ana f stateOld = case f stateOld of
Nothing -> []
Just (value, stateNew) -> value : ana f stateNew
Теперь мы можем реализовать довольно общие функции с помощью ana , например обратный отсчет:
f :: Int -> Maybe (Int, Int)
f current = let oneSmaller = current - 1
in if oneSmaller < 0
then Nothing
else Just (oneSmaller, oneSmaller)
Эта функция будет уменьшать целое число и одновременно выводить его, пока оно не станет отрицательным, после чего будет отмечаться конец списка. Соответственно, ana f 3
вычислю список [2,1,0]
.
Анаморфизмы в других структурах данных
[ редактировать ]Анаморфизм может быть определен для любого рекурсивного типа в соответствии с общим шаблоном, обобщающим вторую версию ana для списков.
Например, развертка древовидной структуры данных
data Tree a = Leaf a | Branch (Tree a) a (Tree a)
заключается в следующем
ana :: (b -> Either a (b, a, b)) -> b -> Tree a
ana unspool x = case unspool x of
Left a -> Leaf a
Right (l, x, r) -> Branch (ana unspool l) x (ana unspool r)
Чтобы лучше понять связь между рекурсивным типом и его анаморфизмом, обратите внимание, что Tree
и List
можно определить так:
newtype List a = List {unCons :: Maybe (a, List a)}
newtype Tree a = Tree {unNode :: Either a (Tree a, a, Tree a))}
Аналогия с ana
появляется при переименовании b
в своем типе:
newtype List a = List {unCons :: Maybe (a, List a)}
anaList :: (list_a -> Maybe (a, list_a)) -> (list_a -> List a)
newtype Tree a = Tree {unNode :: Either a (Tree a, a, Tree a))}
anaTree :: (tree_a -> Either a (tree_a, a, tree_a)) -> (tree_a -> Tree a)
Благодаря этим определениям аргумент конструктора типа имеет тот же тип, что и тип возвращаемого значения первого аргумента типа. ana
, с заменой рекурсивных упоминаний типа на b
.
История
[ редактировать ]Одной из первых публикаций, введших понятие анаморфизма в контекст программирования, была статья « Функциональное программирование с помощью бананов, линз, конвертов и колючей проволоки» . [1] Эрик Мейер и др. , который был в контексте языка программирования Сквиггол .
Приложения
[ редактировать ]Такие функции, как zip
и iterate
являются примерами анаморфизмов. zip
принимает пару списков, скажем, ['a','b','c'] и [1,2,3] и возвращает список пар [('a',1),('b',2) ,('c',3)]. Iterate
переводит вещь x и функцию f из таких вещей в такие вещи и возвращает бесконечный список, полученный в результате многократного применения f, то есть список [x, (fx), (f (fx)), ( f(f(fx))), ...].
zip (a:as) (b:bs) = if (as==[]) || (bs ==[]) -- || means 'or'
then [(a,b)]
else (a,b):(zip as bs)
iterate f x = x:(iterate f (f x))
Чтобы доказать это, мы можем реализовать оба варианта, используя наше общее развертывание: ana
, используя простую рекурсивную процедуру:
zip2 = ana unsp fin
where
fin (as,bs) = (as==[]) || (bs ==[])
unsp ((a:as), (b:bs)) = ((a,b),(as,bs))
iterate2 f = ana (\a->(a,f a)) (\x->False)
В таком языке, как Haskell, даже абстрактные функции fold
, unfold
и ana
являются просто определенными терминами, как мы видели из определений, данных выше.
Анаморфизмы в теории категорий
[ редактировать ]В теории категорий анаморфизмы являются категориальными двойниками катаморфизмов ( а катаморфизмы являются категорическими двойниками анаморфизмов).
Это означает следующее. Предположим, ( A , fin ) финальная F -коалгебра для некоторого эндофунктора F некоторой категории в себя. Таким образом, fin — это морфизм из A в FA , и поскольку он предполагается окончательным, мы знаем, что всякий раз, когда ( X , f ) является другой F -коалгеброй (морфизм f из X в FX ), будет существовать единственный гомоморфизм h из ( X , f ) в ( A , fin ), то есть морфизм h из X в A такой, что fin . ч = Fч . ф . Тогда для каждого такого f обозначим через an f тот однозначно заданный морфизм h .
Другими словами, у нас есть следующее определяющее соотношение при некоторых фиксированных F , A и fin , как указано выше:
Обозначения
[ редактировать ]обозначение ana f: В литературе встречается . Используемые кронштейны известны как кронштейны для линз , после чего анаморфизмы иногда называют линзами .
См. также
[ редактировать ]- Морфизм
- Морфизмы F-алгебр.
- От исходной алгебры к алгебре: катаморфизм
- Анаморфизм, за которым следует катаморфизм: гиломорфизм.
- Расширение идеи катаморфизмов: параморфизм.
- Расширение идеи анаморфизмов: апоморфизм.
Ссылки
[ редактировать ]- ^ Мейер, Эрик ; Фоккинга, Мартен; Патерсон, Росс (1991). «Функциональное программирование с помощью бананов, линз, конвертов и колючей проволоки»: 124–144. CiteSeerX 10.1.1.41.125 .
{{cite journal}}
: Для цитирования журнала требуется|journal=
( помощь )