Анаморфизм - Anamorphism

В компьютерном программировании анаморфизм - это функция, которая генерирует последовательность путем повторного применения функции к ее предыдущему результату. Вы начинаете с некоторого значения A и применяете к нему функцию f, чтобы получить B. Затем вы применяете f к B, чтобы получить C, и так далее, пока не будет достигнуто какое-то условие завершения. Анаморфизм - это функция, которая генерирует список A, B, C и т. Д. Вы можете думать об анаморфизме как разворачивание исходного значения в последовательность.

Приведенное выше описание непрофессионала может быть изложено более формально в теория категорий: анаморфизм коиндуктивный тип обозначает присвоение коалгебра своему уникальному морфизм к последняя коалгебра из эндофунктор. Эти объекты используются в функциональное программирование в качестве разворачивается.

В категоричный дуальный (он же противоположный) анаморфизма - это катаморфизм.

Анаморфизмы в функциональном программировании

В функциональное программирование, анаморфизм является обобщением концепции разворачивается на коиндуктивном списки. Формально анаморфизмы общие функции это может сердечно построить результат определенного тип и который параметризуется функциями, которые определяют следующий отдельный шаг построения.

Рассматриваемый тип данных определяется как наибольшая фиксированная точка ν X. F X функтора F. По универсальности финальных коалгебр существует единственный морфизм коалгебр A → ν X. F X для любого другого F-коалгебра а: А → F A. Таким образом, можно определять функции из типа А _в_ коиндуктивном типе данных путем указания структуры коалгебры а на А.

Пример: потенциально бесконечные списки

Например, тип потенциально бесконечного списки (с элементами фиксированного типа ценить) задается как фиксированная точка [значение] = ν X. значение × X + 1, т.е. список состоит либо из ценить и следующий список, либо он пуст. А (псевдо)Haskell -Определение может выглядеть так:

данные [ценить] = (ценить:[ценить]) | []

Это неподвижная точка функтора Значение F, куда:

данные Может быть а = Только а | Ничегоданные F ценить Икс = Может быть (ценить, Икс)

Легко проверить, действительно ли тип [ценить] изоморфен Значение F [значение], и поэтому [ценить] является фиксированной точкой (также обратите внимание, что в Haskell наименьшая и наибольшая неподвижные точки функторов совпадают, поэтому индуктивные списки аналогичны коиндуктивным потенциально бесконечным спискам.)

В анаморфизм для списков (обычно называемых развернуться) построит (потенциально бесконечный) список из значения состояния. Обычно разворачивание принимает значение состояния Икс и функция ж который дает либо пару значения и нового состояния, либо одноэлемент, чтобы отметить конец списка. Затем анаморфизм начнется с первого начального числа, вычислит, продолжается ли список или заканчивается, а в случае непустого списка добавит вычисленное значение к рекурсивному вызову анаморфизма.

Определение разворачивания в Haskell или анаморфизма для списков, называемое ана, как следует:

ана :: (государственный -> Может быть (ценить, государственный)) -> государственный -> [ценить]ана ж состояниеСтарый = дело ж состояниеСтарый из            Ничего                -> []            Только (ценить, stateNew) -> ценить : ана ж stateNew

Теперь мы можем реализовать довольно общие функции, используя ана, например обратный отсчет:

ж :: Int -> Может быть (Int, Int)ж Текущий = позволять oneSmaller = Текущий - 1            в   если oneSmaller < 0                   тогда Ничего                   еще Только (oneSmaller, oneSmaller)

Эта функция будет уменьшать целое число и одновременно выводить его, пока оно не станет отрицательным, после чего отметит конец списка. Соответственно, Ана Ф 3 вычислит список [2,1,0].

Анаморфизмы в других структурах данных

Анаморфизм может быть определен для любого рекурсивного типа в соответствии с общим шаблоном, обобщающим вторую версию ана для списков.

Например, развертка для древовидной структуры данных

 данные Дерево а = Лист а | Ответвляться (Дерево а) а (Дерево а)

как следует

 ана :: (б -> Либо а (б, а, б)) -> б -> Дерево а ана раскручивать Икс = дело раскручивать Икс из                   Оставили а          -> Лист а                   Правильно (л, Икс, р) -> Ответвляться (ана раскручивать л) Икс (ана раскручивать р)

Чтобы лучше увидеть взаимосвязь между рекурсивным типом и его анаморфизмом, обратите внимание, что Дерево и Список можно определить так:

 Новый тип Список а = Список {unCons :: Может быть (а, Список а)} Новый тип Дерево а = Дерево {unNode :: Либо а (Дерево а, а, Дерево а))}

Аналогия с ана появляется при переименовании б по своему типу:

 Новый тип Список а = Список {unCons :: Может быть (а, Список а)} аналист ::       (list_a       -> Может быть (а, list_a)) -> (list_a -> Список а) Новый тип Дерево а = Дерево {unNode :: Либо а (Дерево а, а, Дерево а))} дерево ::       (tree_a       -> Либо а (tree_a, а, tree_a)) -> (tree_a -> Дерево а)

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

История

Одной из первых публикаций, в которых было введено понятие анаморфизма в контексте программирования, была статья Функциональное программирование с бананами, линзами, конвертами и колючей проволокой,^[1] к Эрик Мейер и другие., что было в контексте Squiggol язык программирования.

Приложения

Функции вроде застегивать и повторять являются примерами анаморфизмов. застегивать берет пару списков, скажем ['a', 'b', 'c'] и [1,2,3], и возвращает список пар [('a', 1), ('b', 2) , ('c', 3)]. Повторять берет вещь x и функцию f от таких вещей к таким вещам и возвращает бесконечный список, полученный в результате повторного применения f, то есть list [x, (fx), (f (fx)), ( f (f (fx))), ...].

 застегивать (а:в качестве) (б:bs) = если (в качестве==[]) || (bs ==[])   - || означает "или"                      тогда [(а,б)]                      еще (а,б):(застегивать в качестве bs)   повторять ж Икс = Икс:(повторять ж (ж Икс))

Чтобы доказать это, мы можем реализовать и то, и другое, используя нашу общую развертку, ана, используя простую рекурсивную процедуру:

 zip2 = ана unsp плавник    куда    плавник (в качестве,bs) = (в качестве==[]) || (bs ==[])     unsp ((а:в качестве), (б:bs)) = ((а,б),(в качестве,bs)) iterate2 ж = ана (\а->(а,ж а)) (\Икс->Ложь)

В таком языке, как Haskell, даже абстрактные функции складывать, развернуться и ана являются просто определенными терминами, как мы видели из определений, данных выше.

Анаморфизмы в теории категорий

В теория категорий, анаморфизмы категоричный дуальный из катаморфизмы (а катаморфизмы - категорически двойственные анаморфизмы).

Это означает следующее. Предполагать (А, плавник) это окончательный F-коалгебра для некоторых эндофунктор F некоторых категория в себя. Таким образом, плавник это морфизм из А к FA, и поскольку предполагается, что он окончательный, мы знаем, что всякий раз, когда (Икс, ж) Другой F-коалгебра (морфизм ж из Икс к FX) будет уникальный гомоморфизм час из (Икс, ж) к (А, плавник), то есть морфизм час из Икс к А такой, что плавник . h = Fh . ж.Тогда для каждого такого ж мы обозначим через ана ж этот однозначно указанный морфизм час.

Другими словами, у нас есть следующие определяющие отношения при некоторых фиксированных F, А, и плавник как указано выше:

${ Displaystyle ч = mathrm {ана} f}$
${ Displaystyle mathrm {fin} circ h = Fh circ f}$

Обозначение

Обозначение для ана ж найдено в литературе ${ Displaystyle [! (е) !]}$ . Используемые скобки известны как кронштейны для линз, после чего анаморфизмы иногда называют линзы.

Смотрите также

Морфизм
Морфизмы F-алгебры
- От начальной алгебры к алгебре: Катаморфизм
- За анаморфизмом следует катаморфизм: Гиломорфизм
- Расширение идеи катаморфизмов: Параморфизм
- Расширение идеи анаморфизмов: Апоморфизм

внешняя ссылка

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

[1] Мейер, Эрик; Фоккинга, Маартен; Патерсон, Росс (1991). «Функциональное программирование с бананами, линзами, конвертами и колючей проволокой». CiteSeerX 10.1.1.41.125. Цитировать журнал требует | журнал = (помощь)

[1]