Corecursion - i kategori teori och datavetenskap , en typ av operation dubbel till rekursion . Vanligtvis används corecursion (i kombination med den lata utvärderingsmekanismen ) för att generera oändliga datastrukturer.
Regeln för att använda corecursion på kodad data är dubbel mot regeln för att använda rekursion på data. Istället för att vika datastrukturen med hjälp av resultatet som erhålls rekursivt baserat på värdet för basfallet , rullar corecursion upp resultatet baserat på det initiala värdet. Det bör noteras att corecursion skapar potentiellt oändliga datastrukturer, medan regelbunden rekursion analyserar (parsar) ändliga datastrukturer vid behov. Normal rekursion är inte tillämplig på kodnamn, eftersom analysprocessen kanske aldrig slutar. Följaktligen kan inte corecursion producera data, eftersom data alltid är ändlig; men varje delresultat av produktiv corecursion är ändlig och kan tolkas som data.
Ett exempel på hur man använder corecursion-mekanismen i Haskell (beräknar en oändlig lista med Fibonacci-tal ):
fibs = 0 : 1 : nästa fibs där nästa ( a : b : c ) = ( a + b ) : nästa ( b : c )Ett annat exempel är att beräkna en oändlig lista med primtal :
primtal = nästa [ 2 .. ] där nästa ( x : xs ) = x : nästa [ y | y <- xs , rem y x /= 0 ]Denna funktion implementerar (ineffektivt) Divisor Search- algoritmen . [ett]
Exemplen som ges i Haskell är inte helt korrekta, eftersom det inte finns något koddataformspråk i språket . I dessa exempel emuleras koddata endast med en obegränsad-definitiv ("oändlig") lista .