Анаморфизм

Чтобы узнать о других значениях, см. Анаморфозы (значения) .

Не путать с катаморфизмом .

В компьютерном программировании анаморфизм — это функция, которая генерирует последовательность путем многократного применения функции к ее предыдущему результату. Вы начинаете с некоторого значения 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.

История

Одной из первых публикаций, введших понятие анаморфизма в контекст программирования, была статья « Функциональное программирование с помощью бананов, линз, конвертов и колючей проволоки» . Эрик Мейер и др. , который был в контексте языка программирования Сквиггол .

Приложения

Такие функции, как 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 , как указано выше:

• $h=\mathrm {ana} \ f$
• $\mathrm {fin} \circ h=Fh\circ f$

Обозначения

обозначение ana f: В литературе встречается $[\!(f)\!]$. Используемые кронштейны известны как кронштейны для линз , после чего анаморфизмы иногда называют линзами .

См. также

• Морфизм
• Морфизмы F-алгебр.
  • От исходной алгебры к алгебре: катаморфизм
  • Анаморфизм, за которым следует катаморфизм: гиломорфизм.
  • Расширение идеи катаморфизмов: параморфизм.
  • Расширение идеи анаморфизмов: апоморфизм.

Внешние ссылки

• Анаморфизмы в Haskell