Катаморфизм в функциональном программировании: обобщение сворачивания списков для алгебраических типов данных. Анамморфизм, гиломорфизм – ключевые понятия.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В функциональном программировании понятие катаморфизма (от древнегреческого κατά "вниз" и μορφή "форма, вид") обозначает единственный гомоморфизм из начальной алгебры в некоторую другую алгебру. Катаморфизмы предоставляют обобщение свёрток списков на произвольные алгебраические типы данных, которые могут быть описаны как начальные алгебры. Двойственным понятием является анаморфизм, обобщающий развёртывания. Гиломорфизм — это композиция анаморфизма и катаморфизма.
In functional programming, the concept of catamorphism (from the Ancient Greek: κατά "downwards" and μορφή "form, shape") denotes the unique homomorphism from an initial algebra into some other algebra. Catamorphisms provide generalizations of folds of lists to arbitrary algebraic data types, which can be described as initial algebras. The dual concept is that of anamorphism that generalize unfolds. A hylomorphism is the composition of an anamorphism followed by a catamorphism.
Определение
Рассмотрим начальную алгебру для некоторого эндофунктора некоторой категории в себя. Здесь есть морфизм из в . Поскольку она начальная, мы знаем, что если есть другая алгебра, то есть морфизм из в , то существует единственный гомоморфизм из в . По определению категории алгебр, это соответствует морфизму из в , обычно также обозначаемому , такому, что . В контексте алгебры, единственный морфизм из начального объекта обозначается и, следовательно, характеризуется следующим соотношением:
Consider an initial algebra for some endofunctor of some category into itself. Here is a morphism from to Since it is initial, we know that whenever is another algebra, i. e. a morphism from to , there is a unique homomorphism from to By the definition of the category of algebra, this corresponds to a morphism from to , conventionally also denoted , such that In the context of algebra, the uniquely specified morphism from the initial object is denoted by and hence characterized by the following relationship:
Терминология и история
Другая нотация, встречающаяся в литературе, – использование открытых скобок, известных как «банановые скобки». В связи с этим катаморфизмы иногда называют «бананами», как отмечается в работах Эрика Мейджера и др. Одной из первых публикаций, представивших понятие катаморфизма в контексте программирования, была статья «Функциональное программирование с бананами, линзами, конвертами и колючей проволокой» Эрика Мейджера и др.
Another notation found in the literature is The open brackets used are known as banana brackets, after which catamorphisms are sometimes referred to as bananas, as mentioned in Erik Meijer et al. One of the first publications to introduce the notion of a catamorphism in the context of programming was the paper “Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire”, by Erik Meijer et al.,
Примеры
Мы приводим ряд примеров, а затем рассматриваем более общий подход к катаморфизмам в языке программирования Haskell.
We give a series of examples, and then a more global approach to catamorphisms, in the Haskell programming language.