Оглавление
Анаморфизм
-
Определение анаморфизма
- Анаморфизм – функция, генерирующая последовательность, повторяя применение к предыдущему результату.
- Начальное значение A применяется к функции f, чтобы получить B, затем B к f, чтобы получить C и так далее.
-
Формальное определение
- В теории категорий анаморфизм обозначает присвоение коалгебре уникального морфизма конечной коалгебры эндофунктора.
-
Применение в функциональном программировании
- Анаморфизмы в функциональном программировании являются обобщением концепции развертывания в коиндуктивных списках.
- Они параметризуются функциями, определяющими следующий шаг построения.
- Тип данных определяется как наибольшая фиксированная точка функтора.
-
Пример: потенциально бесконечные списки
- Тип потенциально бесконечных списков задается как фиксированная точка функтора F, где F X = value × X + 1.
- Анаморфизм для списков позволяет создавать списки из начального состояния и функции, выдающей пары значений и новое состояние или конец списка.
-
Анаморфизмы в других структурах данных
- Анаморфизм может быть определен для любого рекурсивного типа данных.
- Примеры включают анаморфизмы для древовидных структур данных.
-
История и приложения
- Анаморфизмы были введены в программирование Эриком Мейером и др. в статье “Функциональное программирование с бананами, линзами, конвертами и колючей проволокой”.
- Примеры анаморфизмов включают функции zip и iterate.
-
Теория категорий
- Анаморфизмы являются категориальным дуализмом катаморфизмов.
- Для каждой F-коалгебры (A, fin) существует уникальный гомоморфизм h от (X, f) до (A, fin).
-
Обозначение и использование
- Анаморфизмы обозначаются как [f] или [!(f)!].
- Анаморфизмы иногда называют линзами.
Полный текст статьи: