Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік ғылымдағы алгоритмнің түрі
Type of algorithm in computer science
Компьютерлік ғылымда corecursion – рекурсияға қарама-қарсы операцияның түрі. Рекурсия аналитикалық түрде жұмыс істейді, базалық жағдайдан алыс деректерден бастап, оларды кішірек деректерге бөліп, базалық жағдайға жеткенше қайталайды. Ал corecursion синтетикалық түрде жұмыс істейді, базалық жағдайдан бастап оны құрастырады, қайталап, базалық жағдайдан алысқан деректерді шығарады. Қарапайым тілмен айтқанда, corecursive алгоритмдер өздері жасайтын деректерді, олар қолжетімді болған сайын және қажет болғанда, біртіндеп пайдаланады, осы арқылы қосымша деректерді өндіреді. Бұған ұқсас, бірақ ерекше ұғым – генеративтік рекурсия, онда corecursion мен рекурсияға тән нақты "бағыт" болмауы мүмкін. Рекурсия бағдарламаларға кез келген күрделі деректермен жұмыс жасауға мүмкіндік береді, егер оларды қарапайым деректерге (базалық жағдайларға) келтіруге болады. Ал corecursion бағдарламаларға ағын сияқты, кез келген күрделі және мүмкін шексіз дерек құрылымдарын жасауға мүмкіндік береді, егер оларды қарапайым деректерден (базалық жағдайлардан) шекті қадамдар тізбегі арқылы жасауға болады. Рекурсия аяқталуы мүмкін емес, ешқашан базалық жағдайға жетпейді, ал corecursion базалық жағдайдан басталады, сондықтан келесі қадамдарды детерминистік түрде жасайды, бірақ ол шексіз жалғасуы мүмкін (және қатаң бағалау кезінде аяқталмайды) немесе ол өндіргеннен көп тұтынуы мүмкін, соның салдарынан өнімді болмайды. Көптеген функциялар, дәстүрлі түрде рекурсивті деп талданады, альтернативті және, әрине, табиғи түрде, белгілі бір кезеңде аяқталатын corecursive функциялар ретінде түсіндірілуі мүмкін, мысалы, факториал сияқты қайталану қатынастары. Corecursion нәтижесі ретінде шекті және шексіз дерек құрылымдарын шығара алады және өзіне сілтеме жасайтын дерек құрылымдарын қолдана алады. Corecursion жиі жалқау бағалаумен бірге қолданылады, ықтимал шексіз құрылымның шекті жиынтығын ғана өндіру үшін (бірден бүкіл шексіз құрылымды өндіруге тырысудың орнына). Corecursion функционалдық бағдарламалауда ерекше маңызды ұғым болып табылады, онда corecursion және codata жалпы тілдерге шексіз дерек құрылымдарымен жұмыс істеуге мүмкіндік береді.
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.
Мысалдар
Corecursion-ды көбірек таныс рекурсиямен салыстыру арқылы түсінуге болады. Corecursion көбінесе функционалдық бағдарламалауда қызығушылық тудырса да, оны императивті бағдарламалау арқылы мысалмен көрсетуге болады, бұл төменде Python-дағы генератор мүмкіндігін пайдаланып жасалады. Бұл мысалдарда жергілікті айнымалылар қолданылады және оларға императивті (өзгертетін) түрде мәндер беріледі, бірақ бұл таза функционалдық бағдарламалаудағы corecursion үшін қажет емес. Таза функционалдық бағдарламалауда жергілікті айнымалыларға мән берудің орнына, есептелген мәндер өзгермейтін тізбек құрайды, ал бұрынғы мәндерге өзіне сілтеме жасау арқылы қол жеткізіледі (тізбектегі келесі мәндер есептелуі тиіс тізбектегі бұрынғы мәндерге сілтеме жасайды). Мұндай мән берулер императивті парадигмада осыны ғана көрсетеді және есептеулер қайда орындалатынын нақты көрсетеді, бұл түсіндіруді айқындырақ жасайды.
Corecursion can be understood by contrast with recursion, which is more familiar. While corecursion is primarily of interest in functional programming, it can be illustrated using imperative programming, which is done below using the generator facility in Python. In these examples local variables are used, and assigned values imperatively (destructively), though these are not necessary in corecursion in pure functional programming. In pure functional programming, rather than assigning to local variables, these computed values form an invariable sequence, and prior values are accessed by self reference (later values in the sequence reference earlier values in the sequence to be computed). The assignments simply express this in the imperative paradigm and explicitly specify where the computations happen, which serves to clarify the exposition.
Анықтама
Бастапқы дерек типтері белгілі бір типтегі теңдеудің ең кішкентай тұрақты нүктесі (изоморфизмге дейін) ретінде анықталуы мүмкін; изоморфизм бастапқы алгебра арқылы беріледі. Дуалды түрде, соңғы (немесе терминалды) дерек типтері типтегі теңдеудің ең үлкен тұрақты нүктесі ретінде анықталуы мүмкін; изоморфизм содан кейін соңғы коалгебра арқылы беріледі. Егер сөз домені жиынтар мен толық функциялар санаты болса, онда соңғы дерек типтері шексіз, негізсіз мәндерді қамтуы мүмкін, ал бастапқы типтерде мұндай мәндер болмайды. Керісінше, егер сөз домені толық ішінара реттелген жиындар мен үздіксіз функциялар санаты болса, бұл шамамен Haskell бағдарламалау тіліне сәйкес келеді, онда соңғы типтер бастапқы типтермен сәйкес келеді, ал сәйкес соңғы коалгебра мен бастапқы алгебра изоморфизм құрайды. Корекурсия – бұл функцияларды рекурсивті түрде анықтау әдісі, олардың мәндер жиыны (кодомені) соңғы дерек типі болып табылады, бұл әдеттегі рекурсия функцияларды рекурсивті түрде анықтаудан өзгеше, олардың анықталу домені бастапқы дерек типі болып табылады. Төмендегі талқылауда Haskell-те корекурсияны көрсететін бірнеше мысал келтірілген. Шамамен айтқанда, егер осы анықтамалар жиынтар санатына көшірілсе, олар әлі де корекурсивті болар еді. Бұл бейресми қолдану Haskell туралы қолданыстағы оқулықтармен сәйкес келеді. Осы мақалада келтірілген мысалдар корекурсияны анықтау және оның мәнін түсіндіру әрекеттерінен бұрын жасалған.
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. 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. 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. 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. The examples used in this article predate the attempts to define corecursion and explain what it is.
Тарих
Corecursion, циркулярлық бағдарламалау деп аталады, кем дегенде , Джон Хьюз бен Филип Уодлерге қарызы; одан да жалпы формалары әзірленді. Бастапқы себептердің қатарында тиімдірек алгоритмдер жасау (кейбір жағдайларда деректерді бір рет қарауға мүмкіндік беру, бірнеше рет қарау қажеттілігін жою) және функционалдық тілдерде екі жақты байланысқан тізімдер мен кезектер сияқты классикалық дерек құрылымдарын іске асыру болды.
Corecursion, referred to as circular programming, dates at least to , who credits John Hughes and Philip Wadler; more general forms were developed in The original motivations included producing more efficient algorithms (allowing a single pass over data in some cases, instead of requiring multiple passes) and implementing classical data structures, such as doubly linked lists and queues, in functional languages.