Катаморфизм

• Определение катаморфизма

  • Катаморфизм — это гомоморфизм, который обобщает свертки списков на алгебраические типы данных. 
  • Анаморфизм — это обобщение, обратное катаморфизму. 
  • Гилеморфизм — это комбинация анаморфизма и катаморфизма. 

• Определение F-алгебры

  • F-алгебра — это пара (A, in), где A — алгебра, а in — эндофунктор. 
  • Существует уникальный гомоморфизм h от (A, in) к любой другой F-алгебре (X, f). 

• Терминология и история

  • Катаморфизмы иногда называют бананами из-за использования банановых скобок. 
  • Эрик Мейер и другие ввели понятие катаморфизма в контексте программирования в статье «Функциональное программирование с использованием бананов, линз, конвертов и колючей проволоки». 
  • Грант Малкольм дал общее категорическое определение катаморфизма. 

• Примеры катаморфизмов

  • Примеры катаморфизмов включают Maybe-алгебру, список списков и дерево. 
  • В Maybe-алгебре катаморфизм связывает значение «ждать… ждать… ждать… уходить!» с морфизмом. 
  • В списке списков катаморфизм позволяет вычислять значения, такие как «ожидание… ждать… ждать… вперед!». 
  • В дереве катаморфизм вычисляет глубину дерева, используя функцию-преемницу. 

• Теоретические аспекты

  • Теоретически доказано, что F-алгебра, полученная из исходной алгебры с помощью функтора, изоморфна исходной алгебре. 
  • Строгие системы типов позволяют абстрактно определить исходную алгебру функтора. 
  • Рекурсивные катаморфизмы могут быть закодированы с помощью fmap. 

• Рекомендации и дальнейшее чтение

  • Ссылки на дополнительные ресурсы и статьи о катаморфизмах предоставлены в конце статьи.