Анаморфизм

Программирование функции, рекурсивно примененной к предыдущему результату

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

данные [ значение ] = ( значение : [ значение ]) | []     

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

данные Может быть a = Просто a | Ничего данные F значение x = Может быть ( значение , x )              

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

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

Определение развёртки, или анаморфизма для списков, на языке 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 = Лист a | Ветвь ( Дерево a ) a ( Дерево a )            

выглядит следующим образом

 ana :: ( b -> Либо a ( b , a , b )) -> b -> Дерево a ana unspool x = случай unspool x из Left a -> Лист a Right ( l , x , r ) -> Ветвь ( ana unspool l ) x ( ana unspool r )                                       

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

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

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

 newtype Список a = Список { unCons :: Может быть ( a , Список a )} anaList :: ( list_a -> Может быть ( a , список_a )) -> ( list_a -> Список a )                       newtype Дерево a = Дерево { unNode :: Либо a ( Дерево a , a , Дерево a ))} anaTree :: ( tree_a -> Либо a ( tree_a , a , tree_a )) -> ( tree_a -> Дерево a )                           

При таких определениях аргумент конструктора типа имеет тот же тип, что и возвращаемый тип первого аргумента ana, а рекурсивные упоминания типа заменяются на b.

История

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

Приложения

Функции типа 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 == [] ) -- || означает «или», то [( a , b )] else ( a , b ) : ( zip as bs ) iterate f x = x : ( iterate 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 -> Ложь )      

В таком языке, как 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 . h = Fh . f . Тогда для каждого такого f мы обозначаем через ana f этот однозначно заданный морфизм h .

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

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

Обозначение

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

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

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

Ссылки

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

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

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