Корекурсия

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Общие замечания[править | править вики-текст]

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

Примеры[править | править вики-текст]

Пример использования механизма корекурсии на языке 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

Литература[править | править вики-текст]