Корекурсия

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

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

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

Примеры

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

fibs = 0 : 1 : next fibs
  where
    next (a: t@(b:_)) = (a+b) : next t

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

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

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

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

См. также

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

Примечания

1. ↑ Melissa E., «The Genuine Sieve of Eratosthenes», Journal of Functional Programming, Published online by Cambridge University Press 9 October 2008 doi:10.1017/S0956796808007004

Литература

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