Корекурсия

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

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

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

Примеры

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

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

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

primes = eratosthenes [2..]
  where
    eratosthenes (x:xs) = x:eratosthenes (filter ((/= 0).(`mod` x)) xs)

Данная функция реализует алгоритм «решето Эратосфена», причём делает это самым непосредственным образом.

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

Литература

• David Turner (2004-07-28). "Total Functional Programming". Journal of Universal Computer Science 10 (7): 751–768.

См. также

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