В компьютерном программировании анаморфизм - это функция, которая генерирует последовательность путем повторного применения функции к ее предыдущему результату. Вы начинаете с некоторого значения A и применяете к нему функцию f, чтобы получить B. Затем вы применяете f к B, чтобы получить C, и так далее, пока не будет достигнуто какое-то условие завершения. Анаморфизм - это функция, которая генерирует список A, B, C и т. Д. Вы можете думать об анаморфизме как разворачивание начального значения в последовательность.
Описание Вышеуказанной непрофессионала может быть сформулировано более формально в теории категории : анаморфизм из coinductive типа означает присвоение коалгебры своего уникальному морфизма к окончательной коалгебре из в endofunctor . Эти объекты используются в функциональном программировании как развороты .
Категоричны двойное (ака противоположности) от анаморфизма является катаморфизмом .
Анаморфизмы в функциональном программировании [ править ]
В функциональном программировании , анаморфизм является обобщением понятия разверток на coinductive списков . Формально анаморфизмы - это общие функции, которые могут коркурсивно конструировать результат определенного типа и который параметризуется функциями, которые определяют следующий отдельный шаг конструирования.
Рассматриваемый тип данных определяется как наибольшая фиксированная точка ν X. FX функтора F . По универсальному свойству финальных коалгебр существует единственный морфизм коалгебр A → ν X. FX для любой другой F -коалгебры a: A → FA . Таким образом, можно определить функции от типа A _into_ в coinductive типа данных, определяя структуру коалгебры А на А .
Пример: потенциально бесконечные списки [ править ]
В качестве примера тип потенциально бесконечных списков (с элементами фиксированного значения типа ) задается как фиксированная точка [значение] = ν X. значение × X + 1 , т.е. список состоит либо из значения и дополнительного списка, либо он пуст. Определение (псевдо) Haskell может выглядеть так:
данные [ значение ] = ( значение : [ значение ]) | []Это неподвижная точка функтора F value, где:
данные Может быть = Just | Ничего не данные F значение x = Может быть ( значение , x ) Легко проверить, что тип действительно [value]изоморфен F value [value]и, следовательно, [value]является неподвижной точкой. (Также обратите внимание, что в Haskell наименьшая и наибольшая фиксированные точки функторов совпадают, поэтому индуктивные списки аналогичны коиндуктивным потенциально бесконечным спискам.)
Анаморфизм для списков (то , как правило , известны как разворачиваться ) будет строить (потенциально бесконечный) список из государственного значения. Обычно развертывание принимает значение состояния 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 для списков.
Например, развертка для древовидной структуры данных
дерево данных a = Leaf a | Ветвь ( Дерево а ) а ( Дерево а )как следует
ana :: ( b -> Either a ( b , a , b )) -> b -> Tree a ana unpool x = case unpool x of Left a -> Leaf a Right ( l , x , r ) -> Branch ( ана откручивать л ) х ( ана развинчивать г )Чтобы лучше увидеть взаимосвязь между рекурсивным типом и его анаморфизмом, обратите внимание, что 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] с помощью Эрика Мейера и др. , который был в контексте языка программирования Squiggol .
Приложения [ править ]
Функции вроде zipи iterateявляются примерами анаморфизмов. zipберет пару списков, скажем ['a', 'b', 'c'] и [1,2,3], и возвращает список пар [('a', 1), ('b', 2) , ('c', 3)]. Iterateберет вещь x и функцию f от таких вещей к таким вещам и возвращает бесконечный список, полученный в результате повторного применения f, то есть list [x, (fx), (f (fx)), ( f (f (fx))), ...].
zip ( a : as ) ( b : bs ) = if ( as == [] ) || ( bs == [] ) - || означает "или", затем [( a , b )] else ( a , b ) : ( zip as bs ) итерация f x = x : ( итерация f ( f x ))Чтобы доказать это, мы можем реализовать и то, и другое с помощью нашего универсального развертывания ana, используя простую рекурсивную процедуру:
zip2 = ana unsp fin, где 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являются лишь определенными терминами, как мы уже видели из приведенных выше определений.
Анаморфизмы в теории категорий [ править ]
В теории категорий , anamorphisms являются категоричным двойными из катаморфизма (и катаморфизм являются категоричным сопряженным anamorphisms).
Это означает следующее. Предположим, что ( A , fin ) - финальная F -коалгебра для некоторого эндофунктора F некоторой категории в себя. Таким образом, fin является морфизмом из A в FA , и, поскольку он считается окончательным, мы знаем, что всякий раз, когда ( X , f ) является другой F -коалгеброй (морфизм f из X в FX ), будет существовать единственный гомоморфизм h от ( X , f ) до (A , fin ), то есть морфизм h из X в A такой, что fin . h = Fh . f . Тогда для каждого такого f обозначим через ana f однозначно заданный морфизм h .
Другими словами, у нас есть следующие определяющие отношения, учитывая некоторые фиксированные F , A и плавник, как указано выше:
Обозначение [ править ]
Обозначение для ana f, которое можно найти в литературе, есть . Используемые брекеты известны как брекеты для линз , после чего анаморфизмы иногда называют линзами .
![[\! (f) \!]](https://wikimedia.org/api/rest_v1/media/math/render/svg/99f892661108ecb4f29635a1f2416b724dff9f80)
См. Также [ править ]
- Морфизм
- Морфизмы F-алгебр
- От начальной алгебры к алгебре: катаморфизм
- За анаморфизмом следует катаморфизм: гиломорфизм
- Расширение идеи катаморфизмов: параморфизм
- Расширение идеи анаморфизмов: апоморфизм
Ссылки [ править ]
- ^ Мейер, Эрик ; Фоккинга, Маартен; Патерсон, Росс (1991). «Функциональное программирование с бананами, линзами, конвертами и колючей проволокой». CiteSeerX 10.1.1.41.125 . Цитировать журнал требует
|journal=( помощь )
Внешние ссылки [ править ]
- Анаморфизмы в Haskell
