In computer science, corecursion is a type of operation that is dual to recursion. Corecursion is typically used (in conjunction with lazy evaluation) to generate infinite data structures. The rule for primitive corecursion on codata is the dual to that for primitive recursion on data. Instead of descending on the argument, we ascend on the result. Notice that corecursion creates codata, whereas ordinary recursion analyses data. Ordinary recursion is not applicable to the codata because it might not terminate. Conversely, corecursion is not applicable if the result type is data, because data must be finite.

PropertyValue
p:abstract
  • In computer science, corecursion is a type of operation that is dual to recursion. Corecursion is typically used (in conjunction with lazy evaluation) to generate infinite data structures. The rule for primitive corecursion on codata is the dual to that for primitive recursion on data. Instead of descending on the argument, we ascend on the result. Notice that corecursion creates codata, whereas ordinary recursion analyses data. Ordinary recursion is not applicable to the codata because it might not terminate. Conversely, corecursion is not applicable if the result type is data, because data must be finite. Here is an example in Haskell. The following definition produces the list of Fibonacci numbers in linear time: fibs = 0 : 1 : zipWith fibs (tail fibs) The infinite list is produced by corecursion — the latter values of the list are computed on demand starting from the initial two items 0 and 1. This kind of definition is possible only because of lazy evaluation, which allows algorithms on parts of codata to terminate; such techniques are an important part of Haskell programming. An anamorphism is a form of corecursion in the same way that a catamorphism is a form of recursion. The Coq proof assistant supports corecursion and coinduction using the CoFixpoint command. (en)
  • Кореку́рсия — в теории категорий и информатике операция, подобная (дуальная) рекурсии. В основном применима в языке Haskell. Обычно корекурсия используется для генерации бесконечных структур данных. Пример использования механизма корекурсии на языке Haskell : fibs = 0 : 1 : zipWith fibs Другой пример — вычисление бесконечного списка простых чисел: primes = eratosthenes [2..] where eratosthenes = x:eratosthenes (filter xs) Данная функция реализует алгоритм «решето Эратосфена», причём делает это самым непосредственным образом. Категория:Информатика Категория:Теория категорий (ru)
p:hasPhotoCollection
rdfs:comment
  • In computer science, corecursion is a type of operation that is dual to recursion. Corecursion is typically used (in conjunction with lazy evaluation) to generate infinite data structures. The rule for primitive corecursion on codata is the dual to that for primitive recursion on data. Instead of descending on the argument, we ascend on the result. Notice that corecursion creates codata, whereas ordinary recursion analyses data. Ordinary recursion is not applicable to the codata because it might not terminate. Conversely, corecursion is not applicable if the result type is data, because data must be finite. (en)
  • Кореку́рсия — в теории категорий и информатике операция, подобная (дуальная) рекурсии. (ru)
rdfs:label
  • Corecursion (en)
  • Корекурсия (ru)
owl:sameAs
skos:subject
foaf:page
is p:redirect of