Jump to content

Анаморфизм

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

См. также

[ редактировать ]
  1. ^ Мейер, Эрик ; Фоккинга, Мартен; Патерсон, Росс (1991). «Функциональное программирование с помощью бананов, линз, конвертов и колючей проволоки»: 124–144. CiteSeerX   10.1.1.41.125 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 941c906cca94542e9a5b52fc87fb534d__1660661100
URL1:https://arc.ask3.ru/arc/aa/94/4d/941c906cca94542e9a5b52fc87fb534d.html
Заголовок, (Title) документа по адресу, URL1:
Anamorphism - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)