Корекурсия
Кореку́рсия — в теории категорий и информатике тип операции, дуальный к рекурсии. Обычно корекурсия используется (совместно с механизмом ленивых вычислений) для генерации бесконечных структур данных.
Общие замечания
[править | править код]Правило использования корекурсии на коданных дуально правилу применения рекурсии на данных. Вместо свёртывания структуры данных с использованием результата рекурсивно полученного на основе значения для базисного случая, корекурсия развёртывает результат на основе начального значения. Необходимо отметить, что корекурсия создаёт потенциально бесконечные структуры данных, в то время как обычная рекурсия анализирует (разбирает) по необходимости конечные структуры данных. Обычная рекурсия неприменима к коданным, поскольку процесс анализа может никогда не остановиться. Соответственно, корекурсия не может производить данные, поскольку данные всегда конечны; но каждый частичный результат продуктивной корекурсии конечен и может быть интерпретирован как данные.
Примеры
[править | править код]Пример использования механизма корекурсии на языке Haskell (вычисление бесконечного списка чисел Фибоначчи):
fibs = 0 : 1 : next fibs
where
next (a:b:c) = (a+b) : next (b:c)
Другой пример — вычисление бесконечного списка простых чисел:
primes = next [2..]
where
next (x:xs) = x : next [ y | y <- xs, rem y x /= 0 ]
Данная функция (неэффективно) реализует алгоритм «Перебор делителей».[1]
Приведённые примеры на языке Haskell не совсем корректны, поскольку в языке нет идиомы коданных. В указанных примерах коданные только эмулируются при помощи неограниченно-определённого («бесконечного») списка.
См. также
[править | править код]Примечания
[править | править код]- ↑ Melissa E., «The Genuine Sieve of Eratosthenes» Архивная копия от 9 ноября 2017 на Wayback Machine, Journal of Functional Programming, Published online by Cambridge University Press 9 October 2008 doi:10.1017/S0956796808007004
Литература
[править | править код]- David Turner. Total Functional Programming (англ.) // Journal of Universal Computer Science[англ.] : journal. — 2004. — 28 July (vol. 10, no. 7). — P. 751—768.
В другом языковом разделе есть более полная статья Corecursion (англ.). |