Корекурсия кратко

Привет, Вы узнаете о том , что такое корекурсия, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое корекурсия , настоятельно рекомендую прочитать все из категории Информатика.

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

В то время как рекурсия работает аналитически, начиная с данных дальше от базового случая и разбивая их на более мелкие данные и повторяя до тех пор, пока не будет достигнут базовый вариант, corecursion работает синтетически, начиная с базового случая и наращивая его, итеративно производя данные, удаленные из базовый вариант. Проще говоря, базовые алгоритмы используют данные, которые они сами производят, бит за битом, по мере того, как они становятся доступными и необходимыми, для создания дополнительных битов данных. Похожая, но отличная концепция - это генеративная рекурсия, в которой может отсутствовать определенное «направление», присущее коркурсии и рекурсии.

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

Corecursion может создавать как конечные, так и бесконечные структуры данных в качестве результатов и может использовать самодостаточные структуры данных. Об этом говорит сайт https://intellect.icu . Корекурсия часто используется в сочетании с ленивым вычислением , чтобы создать только конечное подмножество потенциально бесконечной структуры (вместо того, чтобы пытаться создать всю бесконечную структуру сразу). Корекурсия - это особенно важная концепция в функциональном программировании , где corecursion и codata позволяют всем языкам работать с бесконечными структурами данных.

История

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

Общие замечания

Правило использования корекурсии на коданных дуально правилу применения рекурсии на данных. Вместо свертывания структуры данных с использованием результата рекурсивно полученного на основе значения для базисного случая, корекурсия развертывает результат на основе начального значения. Необходимо отметить, что корекурсия создает потенциально бесконечные структуры данных, в то время как обычная рекурсия анализирует (разбирает) по необходимости конечные структуры данных. Обычная рекурсия неприменима к коданным, поскольку процесс анализа может никогда не остановиться. Соответственно, корекурсия не может производить данные, поскольку данные всегда конечны; но каждый частичный результат продуктивной корекурсии конечен и может быть интерпретирован как данные.

Примеры

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

Пример использования механизма корекурсии на языке Haskell (вычисление бесконечного списка чисел Фибоначчи):

Другой пример — вычисление бесконечного списка простых чисел:

Данная функция (неэффективно) реализует алгоритм «Перебор делителей».

Приведенные примеры на языке Haskell не совсем корректны, поскольку в языке нет идиомы коданных. В указанных примерах коданные только эмулируются при помощи неограниченно-определенного («бесконечного») списка.

Вау!! 😲 Ты еще не читал? Это зря!

• Коиндукция
• Рекурсия

Исследование, описанное в статье про корекурсия, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое корекурсия и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Информатика