Corecursie
In de informatica is corecursie een operatie type dat een duale is van een recursie. Corecursie wordt typisch in samenhang met luie evaluatie gebruikt om oneindige datastructuren te genereren.
De regel voor primitieve corecursie op codata 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. Mark 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 Coq bewijsassistent ondersteunt corecursie en coinductie en maakt daarbij gebruik van het CoFixpoint commando.
[bewerken] Voorbeeld
Hieronder een voorbeeld in Haskell. De volgende definitie produceert in lineaire tijd de rij van Fibonacci:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
De oneindige lijst wordt geproduceerd door corecursie - de laatste waarden van de lijst worden op aanvraag berekend startend van de initiële twee items 0 en 1. Dit soort definitie is alleen mogelijk vanwege de luie evaluatie, die algoritmen toestaat op delen van de codata te stoppen; zulke technieken zijn een belangrijk onderdeel van het programmeren in Haskell.
[bewerken] Referenties
- David Turner (2004-07-28). Total Functional Programming (Totaal functioneel programmeren). Journal of Universal Computer Science 10 (7): 751–768.
