Анаморфизм

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

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

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

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

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

Анаморфизм в теории категорий[править]

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

Нотация[править]

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

См. также[править]

Ссылки[править]