Анаморфизм

Анаморфизм — понятие из теории категорий, имеющее непосредственное применение в функциональном программировании. Термин происходит от греч. ανα- (наверх, кверху) и μορφή (форма). Является одним из базовых примитивов для описания рекурсивных функций (и, более общо, — рекурсивных процессов). Совместно с сопутствующими понятиями катаморфизма, хиломорфизма и параморфизма может использоваться для представления произвольных рекурсивных функций. Однако, принимая во внимание высокую степень абстракции теории категорий, понятие катаморфизма можно применять в тех областях научного знания, где имеется необходимость в применении примитивов для рекурсии. В том же функциональном программировании данное понятие можно использовать не только для функций, но и в механизме вывода типов (например, в рамках модели статической типизации Хиндли — Милнера).

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

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

Одна из первых публикаций на эту тему в контексте программирования — статья «Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire» («Функциональное программирование при помощи бананов, линз, конвертов и колючей проволоки»), которая описывала анаморфизм на языке программирования Squiggol.

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

В теории категорий анаморфизм является дуальной сущностью к катаморфизму.

Нотация

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

См. также

• Катаморфизм
• Параморфизм
• Хиломорфизм

Ссылки

• Erik Meijer, Maarten Fokkinga, and Ross Paterson. Functional Programming with Bananas, Lenses, Envelopes, and Barbed Wire