Корекурсия в информатике: синтез данных против анализа

Введение

Тип алгоритма в информатике

В информатике, корекурсия — это тип операции, двойственный рекурсии. В то время как рекурсия работает аналитически, начиная с данных, удалённых от базового случая, и разбивая их на более мелкие данные, повторяя этот процесс до достижения базового случая, корекурсия работает синтетически, начиная с базового случая и наращивая его, итеративно производя данные, всё более удалённые от базового случая. Проще говоря, корекурсивные алгоритмы используют данные, которые они сами производят, по частям, по мере их появления и необходимости, для генерации новых данных. Похожей, но отличной концепцией является генеративная рекурсия, которой может не хватать чёткого "направления", присущего корекурсии и рекурсии. Если рекурсия позволяет программам оперировать произвольно сложными данными, при условии, что их можно свести к простым данным (базовым случаям), то корекурсия позволяет программам создавать произвольно сложные и потенциально бесконечные структуры данных, такие как потоки, при условии, что они могут быть построены из простых данных (базовых случаев) в последовательности конечных шагов. В то время как рекурсия может не завершиться, никогда не достигнув базового состояния, корекурсия начинается с базового состояния и, следовательно, производит последующие шаги детерминированно, хотя она может продолжаться бесконечно (и, таким образом, не завершиться при строгой оценке), или потреблять больше ресурсов, чем производит, становясь непродуктивной. Многие функции, традиционно анализируемые как рекурсивные, можно альтернативно и, возможно, более естественно интерпретировать как корекурсивные функции, которые завершаются на определённом этапе, например, рекуррентные соотношения, такие как факториал. Корекурсия может создавать как конечные, так и бесконечные структуры данных в качестве результатов и может использовать самоссылающиеся структуры данных. Корекурсия часто используется в сочетании с ленивыми вычислениями для создания только конечного подмножества потенциально бесконечной структуры (вместо попыток создать всю бесконечную структуру сразу). Корекурсия — особенно важная концепция в функциональном программировании, где корекурсия и кодата позволяют строгим языкам работать с бесконечными структурами данных.

In computer science, corecursion is a type of operation that is dual to recursion. Whereas recursion works analytically, starting on data further from a base case and breaking it down into smaller data and repeating until one reaches a base case, corecursion works synthetically, starting from a base case and building it up, iteratively producing data further removed from a base case. Put simply, corecursive algorithms use the data that they themselves produce, bit by bit, as they become available, and needed, to produce further bits of data. A similar but distinct concept is generative recursion, which may lack a definite "direction" inherent in corecursion and recursion. Where recursion allows programs to operate on arbitrarily complex data, so long as they can be reduced to simple data (base cases), corecursion allows programs to produce arbitrarily complex and potentially infinite data structures, such as streams, so long as it can be produced from simple data (base cases) in a sequence of finite steps. Where recursion may not terminate, never reaching a base state, corecursion starts from a base state, and thus produces subsequent steps deterministically, though it may proceed indefinitely (and thus not terminate under strict evaluation), or it may consume more than it produces and thus become non productive. Many functions that are traditionally analyzed as recursive can alternatively, and arguably more naturally, be interpreted as corecursive functions that are terminated at a given stage, for example recurrence relations such as the factorial. Corecursion can produce both finite and infinite data structures as results, and may employ self referential data structures. Corecursion is often used in conjunction with lazy evaluation, to produce only a finite subset of a potentially infinite structure (rather than trying to produce an entire infinite structure at once). Corecursion is a particularly important concept in functional programming, where corecursion and codata allow total languages to work with infinite data structures.

Примеры

Корекурсию можно понять, рассматривая её в отличие от рекурсии, которая более знакома. Хотя корекурсия представляет наибольший интерес в функциональном программировании, её можно проиллюстрировать с помощью императивного программирования, что и будет сделано ниже с использованием генераторов в Python. В этих примерах используются локальные переменные, которым императивно (разрушающим образом) присваиваются значения, хотя это не обязательно для корекурсии в чистом функциональном программировании. В чистом функциональном программировании, вместо присваивания значений локальным переменным, эти вычисленные значения формируют неизменяемую последовательность, а доступ к предыдущим значениям осуществляется посредством самоссылки (последующие значения в последовательности ссылаются на предыдущие значения для вычисления). Присваивания просто выражают это в императивной парадигме и явно указывают, где происходят вычисления, что помогает прояснить объяснение.

Определение

Начальные типы данных могут быть определены как наименьшая неподвижная точка (до изоморфизма) некоторого уравнения типов; изоморфизм тогда задается начальной алгеброй. Двойственно, финальные (или терминальные) типы данных могут быть определены как наибольшая неподвижная точка уравнения типов; изоморфизм тогда задается финальной коалгеброй. Если областью рассмотрения является категория множеств и тотальных функций, то финальные типы данных могут содержать бесконечные, не вполне определенные значения, в то время как начальные типы – нет. С другой стороны, если областью рассмотрения является категория полных частичных порядков и непрерывных функций, что приблизительно соответствует языку программирования Haskell, то финальные типы совпадают с начальными типами, а соответствующая финальная коалгебра и начальная алгебра образуют изоморфизм. Корекурсия – это техника рекурсивного определения функций, область значений (кодомен) которых является финальным типом данных, двойственная способу, которым обычная рекурсия рекурсивно определяет функции, область определения которых является начальным типом данных. Ниже приводится несколько примеров в Haskell, демонстрирующих особенности корекурсии. Грубо говоря, если бы эти определения были перенесены в категорию множеств, они все равно оставались бы корекурсивными. Такое неформальное использование согласуется с существующими учебниками по Haskell. Примеры, используемые в этой статье, предшествуют попыткам определить и объяснить, что такое корекурсия.

История

Корекурсия, также известная как циклическое программирование, возникла как минимум в 1800 году, и ее появление связывают с работами Джона Хьюза и Филипа Уодлера; более общие формы были разработаны позднее. Первоначальные мотивы включали создание более эффективных алгоритмов (позволяющих однократный проход по данным в некоторых случаях, вместо необходимости множественных проходов) и реализацию классических структур данных, таких как двусвязные списки и очереди, в функциональных языках.