Corecursion (original) (raw)
Кореку́рсия — в теории категорий и информатике тип операции, дуальный к рекурсии. Обычно корекурсия используется (совместно с механизмом ленивых вычислений) для генерации бесконечных структур данных.
| Property | Value |
|---|---|
| dbo:abstract | In computer science, corecursion is a type of operation that is dual to recursion. Whereas recursion works analytically, starting on data further from a base case and breaking it down into smaller data and repeating until one reaches a base case, corecursion works synthetically, starting from a base case and building it up, iteratively producing data further removed from a base case. Put simply, corecursive algorithms use the data that they themselves produce, bit by bit, as they become available, and needed, to produce further bits of data. A similar but distinct concept is generative recursion which may lack a definite "direction" inherent in corecursion and recursion. Where recursion allows programs to operate on arbitrarily complex data, so long as they can be reduced to simple data (base cases), corecursion allows programs to produce arbitrarily complex and potentially infinite data structures, such as streams, so long as it can be produced from simple data (base cases) in a sequence of finite steps. Where recursion may not terminate, never reaching a base state, corecursion starts from a base state, and thus produces subsequent steps deterministically, though it may proceed indefinitely (and thus not terminate under strict evaluation), or it may consume more than it produces and thus become non-productive. Many functions that are traditionally analyzed as recursive can alternatively, and arguably more naturally, be interpreted as corecursive functions that are terminated at a given stage, for example recurrence relations such as the factorial. Corecursion can produce both finite and infinite data structures as results, and may employ self-referential data structures. Corecursion is often used in conjunction with lazy evaluation, to produce only a finite subset of a potentially infinite structure (rather than trying to produce an entire infinite structure at once). Corecursion is a particularly important concept in functional programming, where corecursion and codata allow total languages to work with infinite data structures. (en) In de informatica is corecursie een operatietype dat het duale is van recursie. Corecursie wordt typisch in samenhang met luie evaluatie gebruikt om oneindige datastructuren te representeren. De regel voor primitieve corecursie op is de duale van de regel voor primitieve recursie op data. In plaats van de argumenten van boven naar beneden te bekijken, lopen we de resultaten van beneden naar boven door. Merk op dat de corecursie (mogelijk oneindige) codata creëert, terwijl de gewone recursie (noodzakelijkerwijs eindige) data analyseert. Gewone recursie is niet toepasbaar op de codata, omdat de recursie mogelijk niet eindigt. Omgekeerd is corecursie niet toepasbaar als het resultaattype van de data eindig moet zijn. Een anamorfisme is op dezelfde manier een vorm van corecursie als een catamorfisme een vorm van recursie is. De bewijsassistent ondersteunt corecursie en en maakt daarbij gebruik van het CoFixpoint commando. (nl) Кореку́рсия — в теории категорий и информатике тип операции, дуальный к рекурсии. Обычно корекурсия используется (совместно с механизмом ленивых вычислений) для генерации бесконечных структур данных. (ru) 共递归在计算机科学重视一类操作，与递归在范畴论上对偶。因而递归是分析地工作，把数据分解为更小的数据直至达到基本情况。共递归是合成地工作，从基本情况构造出数据。共递归的数据是自己一点一点构造出来的。一个类似但不同的概念是（generative recursion）。 共递归常与惰性求值配合，产生一个潜在无穷结构的有限子集。 (zh) В інформатиці, корекурсія — це операція двоїста до рекурсії. Тоді як рекурсія працює аналітично, починаючи з даних далеких від базового випадку, розбиває їх на менші шматки, і повторюється допоки не досягне базового випадку, корекурсія працює синтетично, починаючи з базового випадку і просувається ітеративно продукуючи дані далі віддалені від базового випадку. Просто кажучи, корекурсивні алгоритми використовують дані які самі ж створюють, крок за кроком, по мірі того як вони стають доступними і потрібними для утворення нових даних. У той час як рекурсія дозволяє програмам діяти на даних довільної складності, допоки їх можна звести до простих даних (базових випадків), корекурсія дозволяє програмам видавати довільно складні і потенціально нескінченні структури даних, такі як потоки, поки це можливо із простих даних (базових випадків). Тоді як рекурсія може не закінчитись, ніколи не досягши базового випадку, корекурсія починає з базового випадку, і отже продукує наступні кроки детерміністично, хоча вона може продовжуватись нескінченно (і також не завершитись за умови ), або вона може споживати більше ніж видавати і таким чином стати непродуктивною. Багато функцій, що традиційно аналізуються як рекурсивні можна представити як корекурсивні, що завершуються на певній стадії, наприклад рекурентні співвідношення такі як факторіали. Корекурсія може створювати скінченні і нескінченні структури даних, і може задіювати автореферентні структури даних. Корекурсію часто використовують разом із лінивими обчисленнями, для того, щоб утворити лише скінченну підмножину потенційно нескінченної структури (замість спроби отримати повну нескінченну структуру одразу). Корекурсія є дуже важливою концепцією у функціональному програмуванні, де корекурсія і кодані дозволяють цілковито функціональним мовам працювати із нескінченними структурами даних. (uk) |
| dbo:wikiPageExternalLink | http://themonadreader.wordpress.com/2009/07/29/issue-14/ http://wrap.warwick.ac.uk/46312/1/WRAP_Smyth_cs-rr-014.pdf http://www.press.uchicago.edu/presssite/metadata.epl%3Fmode=synopsis&bookkey=3630257 http://code.activestate.com/recipes/576961/ http://www.jucs.org/jucs_10_7/total_functional_programming http://www.cs.nott.ac.uk/~gmh/bib.html%23corecursion https://web.archive.org/web/20100621142601/http:/www.press.uchicago.edu/presssite/metadata.epl%3Fmode=synopsis&bookkey=3630257 http://citeseerx.ist.psu.edu/viewdoc/summary%3Fdoi=10.1.1.32.5446 http://dl.acm.org/citation.cfm%3Fid=189973.189981 http://homepages.cwi.nl/~jve/HR/ http://www.csse.monash.edu.au/~lloyd/tildeFP/1989SPE/ |
| dbo:wikiPageID | 1338683 (xsd:integer) |
| dbo:wikiPageLength | 29289 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1100572066 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Queue_(abstract_data_type) dbr:Tail_call dbr:Total_language dbr:Denotational_semantics dbc:Articles_with_example_Haskell_code dbc:Recursion dbr:Apomorphism dbr:Up_to_isomorphism dbr:Infinite_set dbr:Initial_algebra dbr:Coq dbr:Anamorphism dbr:Generative_recursion dbr:Generator_(computer_programming) dbr:Paramorphism dbr:Coinduction dbr:Gordon_Plotkin dbr:Branching_factor dbr:SIAM_Journal_on_Computing dbr:Call_stack dbr:Stack_(abstract_data_type) dbr:Stream_(computing) dbr:Complete_partial_order dbr:Computer_science dbr:Functional_programming dbr:John_Hughes_(computer_scientist) dbc:Functional_programming dbr:Category_of_sets dbr:Tree_traversal dbr:Data_structure dbr:Dual_(category_theory) dbr:Codata_(computer_science) dbr:Lazy_evaluation dbr:Finite_set dbr:Breadth-first_search dbr:Fold_(higher-order_function) dbr:Isomorphism dbr:Iterator dbr:Scott_continuity dbr:Recurrence_relation dbr:Recursion dbr:Haskell_(programming_language) dbr:Fibonacci_numbers dbr:Fibonacci_sequence dbc:Category_theory dbc:Theoretical_computer_science dbc:Articles_with_example_Python_(programming_language)_code dbr:Jeremy_Gibbons dbr:Bisimulation dbr:Assignment_(computer_science) dbc:Self-reference dbr:Philip_Wadler dbr:Greatest_fixpoint dbr:Initial_and_terminal_objects dbr:Catamorphism dbr:Recursion_(computer_science) dbr:Self-reference dbr:Unfold_(higher-order_function) dbr:F-coalgebra dbr:Factorial dbr:Non-well-founded_set_theory dbr:Parallel_assignment dbr:Breadth-first dbr:Pattern-matching dbr:Least_fixpoint dbr:Primitive_recursion dbr:Depth-first |
| dbp:wikiPageUsesTemplate | dbt:Cite_techreport dbt:Anchor dbt:Citation dbt:Cite_book dbt:Cite_journal dbt:Cite_web dbt:Cleanup dbt:Distinguish dbt:Efn dbt:Essay dbt:Harv dbt:Nobreak dbt:Notelist dbt:Refbegin dbt:Refend dbt:Reflist dbt:Technical |
| dcterms:subject | dbc:Articles_with_example_Haskell_code dbc:Recursion dbc:Functional_programming dbc:Category_theory dbc:Theoretical_computer_science dbc:Articles_with_example_Python_(programming_language)_code dbc:Self-reference |
| gold:hypernym | dbr:Operation |
| rdf:type | owl:Thing dbo:MilitaryConflict |
| rdfs:comment | Кореку́рсия — в теории категорий и информатике тип операции, дуальный к рекурсии. Обычно корекурсия используется (совместно с механизмом ленивых вычислений) для генерации бесконечных структур данных. (ru) 共递归在计算机科学重视一类操作，与递归在范畴论上对偶。因而递归是分析地工作，把数据分解为更小的数据直至达到基本情况。共递归是合成地工作，从基本情况构造出数据。共递归的数据是自己一点一点构造出来的。一个类似但不同的概念是（generative recursion）。 共递归常与惰性求值配合，产生一个潜在无穷结构的有限子集。 (zh) In computer science, corecursion is a type of operation that is dual to recursion. Whereas recursion works analytically, starting on data further from a base case and breaking it down into smaller data and repeating until one reaches a base case, corecursion works synthetically, starting from a base case and building it up, iteratively producing data further removed from a base case. Put simply, corecursive algorithms use the data that they themselves produce, bit by bit, as they become available, and needed, to produce further bits of data. A similar but distinct concept is generative recursion which may lack a definite "direction" inherent in corecursion and recursion. (en) In de informatica is corecursie een operatietype dat het duale is van recursie. Corecursie wordt typisch in samenhang met luie evaluatie gebruikt om oneindige datastructuren te representeren. De regel voor primitieve corecursie op is de duale van de regel voor primitieve recursie op data. Een anamorfisme is op dezelfde manier een vorm van corecursie als een catamorfisme een vorm van recursie is. De bewijsassistent ondersteunt corecursie en en maakt daarbij gebruik van het CoFixpoint commando. (nl) В інформатиці, корекурсія — це операція двоїста до рекурсії. Тоді як рекурсія працює аналітично, починаючи з даних далеких від базового випадку, розбиває їх на менші шматки, і повторюється допоки не досягне базового випадку, корекурсія працює синтетично, починаючи з базового випадку і просувається ітеративно продукуючи дані далі віддалені від базового випадку. Просто кажучи, корекурсивні алгоритми використовують дані які самі ж створюють, крок за кроком, по мірі того як вони стають доступними і потрібними для утворення нових даних. (uk) |
| rdfs:label | Corecursion (en) Corecursie (nl) Корекурсия (ru) 共递归 (zh) Корекурсія (uk) |
| owl:differentFrom | dbr:Mutual_recursion |
| owl:sameAs | freebase:Corecursion wikidata:Corecursion dbpedia-nl:Corecursion dbpedia-ru:Corecursion dbpedia-uk:Corecursion dbpedia-zh:Corecursion https://global.dbpedia.org/id/2Nxd9 |
| prov:wasDerivedFrom | wikipedia-en:Corecursion?oldid=1100572066&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Corecursion |
| is dbo:wikiPageRedirects of | dbr:Corecursive dbr:Co-recursion dbr:Co-recursive |
| is dbo:wikiPageWikiLink of | dbr:Tail_call dbr:Corecursive dbr:Apomorphism dbr:Initial_algebra dbr:Anamorphism dbr:Generator_(computer_programming) dbr:Coinduction dbr:Snap!_(programming_language) dbr:Total_functional_programming dbr:Tree_traversal dbr:Haskell_features dbr:Curry–Howard_correspondence dbr:Fold_(higher-order_function) dbr:Recursion dbr:Recursion_(computer_science) dbr:Stream_(abstract_data_type) dbr:Co-recursion dbr:Co-recursive |
| is foaf:primaryTopic of | wikipedia-en:Corecursion |