Arabic
Bulgarian
Chinese
Croatian
Czech
Danish
Dutch
English
Estonian
Finnish
French
German
Greek
Hebrew
Hindi
Hungarian
Icelandic
Indonesian
Italian
Japanese
Korean
Latvian
Lithuanian
Malagasy
Norwegian
Persian
Polish
Portuguese
Romanian
Russian
Serbian
Slovak
Slovenian
Spanish
Swedish
Thai
Turkish
Vietnamese

Arabic
Bulgarian
Chinese
Croatian
Czech
Danish
Dutch
English
Estonian
Finnish
French
German
Greek
Hebrew
Hindi
Hungarian
Icelandic
Indonesian
Italian
Japanese
Korean
Latvian
Lithuanian
Malagasy
Norwegian
Persian
Polish
Portuguese
Romanian
Russian
Serbian
Slovak
Slovenian
Spanish
Swedish
Thai
Turkish
Vietnamese

definition of Wikipedia

Advertizing ▼

This article may be too technical for most readers to understand. (November 2010) |

This article needs attention from an expert on the subject. (November 2010) |

In computer science, **corecursion** is a type of operation that is dual to recursion. Corecursion and **codata** allow total languages to work with infinite data structures such as streams. Corecursion is often used in conjunction with lazy evaluation. Corecursion can produce both finite and infinite data structures as result, and may employ self-referential data structures. Put simply, it is about algorithms using the data which they themselves produce, bit by bit, as they become available, and needed, to produce further bits of data.

## Contents |

Initial data types can be defined as being the least fixpoint (up to isomorphism) of some type equation; the isomorphism is then given by an initial algebra. Dually, final (or terminal) data types can be defined as being the greatest fixpoint of a type equation; the isomorphism is then given by a final coalgebra.

If the domain of discourse is the category of sets and total functions, then final data types may contain infinite, non-wellfounded values, whereas initial types do not.^{[1]}^{[2]} On the other hand, if the domain of discourse is the category of complete partial orders and continuous functions, which corresponds roughly to the Haskell programming language, then final types coincide with initial types, and the corresponding final coalgebra and initial algebra form an isomorphism.^{[3]}

Corecursion is then a technique for recursively defining functions whose range (codomain) is a final data type, dual to the way that ordinary recursion recursively defines functions whose domain is an initial data type.^{[4]}

The discussion below provides several examples in Haskell that distinguish corecursion. Roughly speaking, if one were to port these definitions to the category of sets, they would still be corecursive. This informal usage is consistent with existing textbooks about Haskell.^{[5]} Also note that the examples used in this article predate the attempts to define corecursion and explain what it is.

The rule for *primitive corecursion* on codata is the dual to that for primitive recursion on data. Instead of descending on the argument by pattern-matching on its constructors (that *were called up before*, somewhere, so we receive a ready-made datum and get at its constituent sub-parts, i.e. "fields"), we ascend on the result by filling-in its "destructors" (or "observers", that *will be called afterwards*, somewhere - so we're actually calling a constructor, creating another bit of the result to be observed later on). Thus corecursion *creates* (potentially infinite) codata, whereas ordinary recursion *analyses* (necessarily finite) data. Ordinary recursion might not be applicable to the codata because it might not terminate. Conversely, corecursion is not strictly necessary 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 : next fibs where next (a: t@(b:_)) = (a+b):next t

This infinite list depends on lazy evaluation; elements are computed on an as-needed basis, and only finite prefixes are ever explicitly represented in memory. This feature allows algorithms on parts of codata to terminate; such techniques are an important part of Haskell programming.

This example employs a self-referential *data structure*. Ordinary recursion makes use of self-referential *functions*, but does not accommodate self-referential data. However, this is not essential to the Fibonacci example. It can be rewritten as follows:

fibs = fibgen (0,1) fibgen (x,y) = x : fibgen (y,x+y)

This employs only self-referential function to construct the result. If it were used with strict list constructor it would be an example of runaway recursion, but with non-strict list constructor it (corecursively) produces an indefinitely defined list.

This shows how it can be done in Python:^{[6]}

from itertools import tee, chain, islice, imap def add(x,y): return (x + y) def fibonacci(): def deferred_output(): for i in output: yield i result, c1, c2 = tee(deferred_output(), 3) paired = imap(add, c1, islice(c2, 1, None)) output = chain([0, 1], paired) return result for i in islice(fibonacci(),20): print i

Corecursion need not produce an infinite object; a corecursive queue^{[7]} is a particularly good example of this phenomenon. The following definition produces a breadth-first traversal of a binary tree in linear time:

data Tree a b = Leaf a | Branch b (Tree a b) (Tree a b) bftrav :: Tree a b -> [Tree a b] bftrav tree = queue where queue = tree : trav 1 queue trav 0 q = [] trav len (Leaf _ : q) = trav (len-1) q trav len (Branch _ l r : q) = l : r : trav (len+1) q

This definition takes an initial tree and produces list of subtrees. This list serves a dual purpose as both the queue and the result. It is finite if and only if the initial tree is finite. The length of the queue must be explicitly tracked in order to ensure termination; this can safely be elided if this definition is applied only to infinite trees. Even if the result is finite, this example depends on lazy evaluation due to the use of self-referential data structures.

Another particularly good example gives a solution to the problem of breadth-first labelling.^{[8]} The function `label`

visits every node in a binary tree in a breadth first fashion, and replaces each label with an integer, each subsequent integer is bigger than the last by one. This solution employs a self-referential data structure, and the binary tree can be finite or infinite.

label :: Tree a b -> Tree Int Int label t = t' where (t',ns) = label' t (1:ns) label' :: Tree a b -> [Int] -> (Tree Int Int, [Int]) label' (Leaf _ ) (n:ns) = (Leaf n , n+1 : ns ) label' (Branch _ l r) (n:ns) = (Branch n l' r' , n+1 : ns'') where (l',ns' ) = label' l ns (r',ns'') = label' r ns'

An apomorphism is a form of corecursion in the same way that a paramorphism is a form of recursion.

The Coq proof assistant supports corecursion and coinduction using the CoFixpoint command.

- Lloyd Allison (1989-04). "Circular Programs and Self-Referential Structures".
*Software Practice and Experience***19**(2): 99–109. DOI:10.1002/spe.4380190202. http://www.csse.monash.edu.au/~lloyd/tildeFP/1989SPE/. - Geraint Jones and Jeremy Gibbons (1992).
*Linear-time breadth-first tree algorithms: An exercise in the arithmetic of folds and zips*(Technical report). Dept of Computer Science, University of Auckland. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.5446. - Jon Barwise and Lawrence S Moss (1996-06).
*Vicious Circles*. Center for the Study of Language and Information. ISBN 978-1-57586-009-1. http://www.press.uchicago.edu/presssite/metadata.epl?mode=synopsis&bookkey=3630257. - Lawrence S Moss and Norman Danner (1997). "On the Foundations of Corecursion".
*Logic Journal of the IGPL***5**(2): 231–257. DOI:10.1093/jigpal/5.2.231. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.4243. - Kees Doets and Jan van Eijck (2004-05).
*The Haskell Road to Logic, Maths, and Programming*. King's College Publications. ISBN 978-0-9543006-9-2. http://homepages.cwi.nl/~jve/HR/. - David Turner (2004-07-28). "Total Functional Programming".
*Journal of Universal Computer Science***10**(7): 751–768. DOI:10.3217/jucs-010-07-0751. http://www.jucs.org/jucs_10_7/total_functional_programming. - Jeremy Gibbons and Graham Hutton (2005-04). "Proof methods for corecursive programs".
*Fundamenta Informaticae Special Issue on Program Transformation***66**(4): 353–366. http://www.cs.nott.ac.uk/~gmh/bib.html#corecursion. - Leon P Smith (2009-07-29), "Lloyd Allison's Corecursive Queues: Why Continuations Matter",
*The Monad Reader*(14): 37–68, http://themonadreader.wordpress.com/2009/07/29/issue-14/ - Raymond Hettinger (2009-11-19). "Recipe 576961: Technique for cyclical iteration". http://code.activestate.com/recipes/576961/.
- M. B. Smyth and G. D. Plotkin (1982). "The Category-Theoretic Solution of Recursive Domain Equations".
*SIAM Journal on Computing***11**(4): 761–783. DOI:10.1137/0211062.

sensagent's content

- definitions
- synonyms
- antonyms
- encyclopedia

Dictionary and translator for handheld

New : sensagent is now available on your handheld

Advertising ▼

Webmaster Solution

Alexandria

A windows (pop-into) of information (full-content of Sensagent) triggered by double-clicking any word on your webpage. Give contextual explanation and translation from your sites !

SensagentBox

With a SensagentBox, visitors to your site can access reliable information on over 5 million pages provided by Sensagent.com. Choose the design that fits your site.

Business solution

Improve your site content

Add new content to your site from Sensagent by XML.

Crawl products or adds

Get XML access to reach the best products.

Index images and define metadata

Get XML access to fix the meaning of your metadata.

Please, email us to describe your idea.

Lettris

Lettris is a curious tetris-clone game where all the bricks have the same square shape but different content. Each square carries a letter. To make squares disappear and save space for other squares you have to assemble English words (left, right, up, down) from the falling squares.

boggle

Boggle gives you 3 minutes to find as many words (3 letters or more) as you can in a grid of 16 letters. You can also try the grid of 16 letters. Letters must be adjacent and longer words score better. See if you can get into the grid Hall of Fame !

English dictionary

Main references

Most English definitions are provided by WordNet .

English thesaurus is mainly derived from The Integral Dictionary (TID).

English Encyclopedia is licensed by Wikipedia (GNU).

Copyrights

The wordgames anagrams, crossword, Lettris and Boggle are provided by Memodata.

The web service Alexandria is granted from Memodata for the Ebay search.

The SensagentBox are offered by sensAgent.

Translation

Change the target language to find translations.

Tips: browse the semantic fields (see From ideas to words) in two languages to learn more.

last searches on the dictionary :

CORRIE SANDERS ·
GORMAZ ·
Jung-Keun ·
Ako Abdul-Samad ·
Bullockornis ·
LICENSEES ·
Liquid Todd ·
child care ·
Al Washington ·
Alan A'Court ·

3500 online visitors

computed in 0.140s

I would like to report:

section :

a spelling or a grammatical mistake

an offensive content(racist, pornographic, injurious, etc.)

a copyright violation

an error

a missing statement

other

please precise: