Was ist der Unterschied zwischen Rekursion und Corecursion?

Was ist der Unterschied zwischen diesen?

• Rekursion
• Kernkurs

Auf Wikipedia gibt es nur wenige Informationen und keinen eindeutigen Code, der diese Begriffe erklärt.

Was sind einige sehr einfache Beispiele, die diese Begriffe erklären?

Wie ist Corecursion das Duale der Rekursion?

Gibt es klassische CoreCusive-Algorithmen?

Es gibt eine Reihe guter Betrachtungsweisen. Für mich ist es am einfachsten, über die Beziehung zwischen "induktiven" und "koinduktiven Definitionen" nachzudenken.

Eine induktive Definition einer Menge geht so.

Die Menge "Nat" ist definiert als die kleinste Menge, so dass "Zero" in Nat ist, und wenn n in Nat ist, ist "Succ n" in Nat.

Welches entspricht der folgenden Ocaml

type nat = Zero | Succ of nat

Eine Sache, die an dieser Definition zu beachten ist, ist die Zahl

omega = Succ(omega)

ist KEIN Mitglied dieses Sets. Warum? Nehmen wir an, dass dies der Fall war, und betrachten Sie nun die Menge N, die dieselben Elemente wie Nat enthält, außer dass sie kein Omega enthält. Offensichtlich ist Null in N, und wenn y in N ist, ist Succ (y) in N, aber N ist kleiner als Nat, was ein Widerspruch ist. Also, Omega ist nicht in Nat.

Oder vielleicht nützlicher für einen Informatiker:

Wenn eine Menge "a" gegeben ist, wird die Menge "Liste von a" als die kleinste Menge definiert, so dass "Nil" in Liste von a ist und wenn xs in Liste von a ist und x in einem "Cons x xs" ist. ist in der Liste von a.

Was sowas entspricht

type 'a list = Nil | Cons of 'a * 'a list

Das operative Wort ist hier "kleinste". Wenn wir nicht "kleinste" sagen würden, könnten wir nicht sagen, ob das Set Nat eine Banane enthält!

Nochmal,

zeros = Cons(Zero,zeros)

ist keine gültige Definition für eine Liste von Nats, genau wie Omega keine gültige Nat war.

Induziertes Definieren von Daten auf diese Weise ermöglicht es uns, Funktionen zu definieren, die mithilfe von Rekursion darauf arbeiten

let rec plus a b = match a with
                   | Zero    -> b
                   | Succ(c) -> let r = plus c b in Succ(r)

wir können dann Tatsachen darüber beweisen, wie "plus eine Null = a" durch Induktion (speziell strukturelle Induktion)

Unser Beweis erfolgt durch strukturelle Induktion auf a.
Für den Basisfall sei a Null. plus Zero Zero = match Zero with |Zero -> Zero | Succ(c) -> let r = plus c b in Succ(r)so wissen wir es plus Zero Zero = Zero. Lass aein nat sein. Nehmen wir die induktive Hypothese an, dass plus a Zero = a. Wir zeigen nun, dass plus (Succ(a)) Zero = Succ(a)dies offensichtlich ist, da plus (Succ(a)) Zero = match a with |Zero -> Zero | Succ(a) -> let r = plus a Zero in Succ(r) = let r = a in Succ(r) = Succ(a) durch Induktion plus a Zero = afür alle ain nat

Wir können natürlich interessantere Dinge beweisen, aber das ist die allgemeine Idee.

Bisher haben wir uns mit induktiv definierten Daten befasst, die wir erhalten haben, indem wir sie zur "kleinsten" Menge gemacht haben. Nun wollen wir mit coinduktiv definierten Codaten arbeiten, die wir erhalten, indem wir sie zur größten Menge machen.

Damit

Sei a eine Menge. Die Menge "Stream of a" ist definiert als die größte Menge, so dass x für jedes x im Stream von a aus dem geordneten Paar (Kopf, Schwanz) besteht, sodass sich Kopf in a und Schwanz in Stream of a befindet

In Haskell würden wir dies ausdrücken als

data Stream a = Stream a (Stream a) --"data" not "newtype"

Tatsächlich verwenden wir in Haskell normalerweise die eingebauten Listen, die ein geordnetes Paar oder eine leere Liste sein können.

data [a] = [] | a:[a]

Banana ist ebenfalls kein Mitglied dieses Typs, da es sich nicht um ein geordnetes Paar oder eine leere Liste handelt. Aber jetzt können wir sagen

ones = 1:ones

und das ist eine vollkommen gültige Definition. Darüber hinaus können wir auf diesen Co-Daten eine Co-Rekursion durchführen. Tatsächlich ist es möglich, dass eine Funktion sowohl ko-rekursiv als auch rekursiv ist. Während Rekursion durch die Funktion definiert wurde, deren Domäne aus Daten besteht, bedeutet Ko-Rekursion nur, dass es sich bei der Ko-Domäne (auch als Bereich bezeichnet) um Ko-Daten handelt. Primitive Rekursion bedeutete, sich immer auf kleinere Daten zu "berufen", bis die kleinsten Daten erreicht waren. Primitive Co-Rekursion "ruft sich immer von selbst" auf Daten auf, die größer oder gleich dem sind, was Sie zuvor hatten.

ones = 1:ones

ist primitiv ko-rekursiv. Während die Funktion map(wie "foreach" in imperativen Sprachen) sowohl primitiv rekursiv als auch primitiv ko-rekursiv ist.

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = (f x):map f xs

Gleiches gilt für die Funktion, zipWithdie eine Funktion und ein Listenpaar aufnimmt und mit dieser Funktion zusammenfügt.

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (a:as) (b:bs) = (f a b):zipWith f as bs
zipWith _ _ _           = [] --base case

Das klassische Beispiel für funktionale Sprachen ist die Fibonacci-Sequenz

fib 0 = 0
fib 1 = 1
fib n = (fib (n-1)) + (fib (n-2))

Das ist primitiv rekursiv, kann aber eleganter als unendliche Liste ausgedrückt werden

fibs = 0:1:zipWith (+) fibs (tail fibs)
fib' n = fibs !! n --the !! is haskell syntax for index at

Ein interessantes Beispiel für Induktion / Coinduktion beweist, dass diese beiden Definitionen dasselbe berechnen. Dies ist eine Übung für den Leser.

Grundsätzlich ist corecursion Rekursion Akkumulator-Stil , den Aufbau sein Ergebnisses auf dem Weg nach vorne aus dem Ausgangsfall, während der reguläre Rekursion sein Ergebnis auf dem Weg zurück vom baut Basisfall.

(spricht jetzt Haskell). Das ist der Grund, warum foldr(mit einer strengen Kombinationsfunktion) eine Rekursion ausdrückt und foldl'(mit einem strengen Kamm. F.) / scanl/ until/ iterate/ unfoldr/ Usw. eine Kernkursion ausdrückt. Corecursion ist überall. foldrmit nicht strengen Kamm. f. drückt die Schweifrekursion modulo cons aus .

Und Haskells vorsichtige Rekursion ist genau wie die modulo Nachteile der Schwanzrekursion .

Das ist Rekursion:

fib n | n==0 = 0
      | n==1 = 1
      | n>1  = fib (n-1) + fib (n-2)

fib n = snd $ g n
  where
    g n | n==0 = (1,0)
        | n>0  = let { (b,a) = g (n-1) } in (b+a,b)

fib n = snd $ foldr (\_ (b,a) -> (b+a,b)) (1,0) [n,n-1..1]

(gelesen $als "von"). Das ist Corecursion:

fib n = g (0,1) 0 n where
  g n (a,b) i | i==n      = a 
              | otherwise = g n (b,a+b) (i+1)

fib n = fst.snd $ until ((==n).fst) (\(i,(a,b)) -> (i+1,(b,a+b))) (0,(0,1))
      = fst $ foldl (\(a,b) _ -> (b,a+b)) (0,1) [1..n]
      = fst $ last $ scanl (\(a,b) _ -> (b,a+b)) (0,1) [1..n]
      = fst (fibs!!n)  where  fibs = scanl (\(a,b) _ -> (b,a+b)) (0,1) [1..]
      = fst (fibs!!n)  where  fibs = iterate (\(a,b) -> (b,a+b)) (0,1)
      = (fibs!!n)  where  fibs = unfoldr (\(a,b) -> Just (a, (b,a+b))) (0,1)
      = (fibs!!n)  where  fibs = 0:1:map (\(a,b)->a+b) (zip fibs $ tail fibs)
      = (fibs!!n)  where  fibs = 0:1:zipWith (+) fibs (tail fibs)
      = (fibs!!n)  where  fibs = 0:scanl (+) 1 fibs
      = .....

Falten: http://en.wikipedia.org/wiki/Fold_(higher-order_function)

Überprüfen Sie dies auf Vitomir Kovanovic 's Blog . Ich fand es auf den Punkt:

Lazy Evaluation in einer sehr netten Funktion, die in Programmiersprachen mit funktionalen Programmierfunktionen wie lisp, haskell, python usw. zu finden ist. Dies bedeutet, dass die Bewertung des Variablenwerts auf die tatsächliche Verwendung dieser Variablen verzögert wird.

Wenn Sie zum Beispiel eine Liste von Millionen Elementen mit so etwas erstellen (defn x (range 1000000))möchten, wird diese nicht tatsächlich erstellt, sondern nur angegeben, und wenn Sie diese Variable zum ersten Mal wirklich verwenden, zum Beispiel, wenn Sie das zehnte Element von möchten Dieser Listeninterpreter erstellt nur die ersten 10 Elemente dieser Liste. Der erste Durchlauf von (take 10 x) erstellt diese Elemente also tatsächlich, und alle nachfolgenden Aufrufe derselben Funktion funktionieren mit bereits vorhandenen Elementen.

Dies ist sehr nützlich, da Sie unbegrenzte Listen ohne Speicherfehler erstellen können. Die Liste ist sehr umfangreich, genau wie viel Sie angefordert haben. Wenn Ihr Programm mit großen Datensammlungen arbeitet, kann es bei der Verwendung dieser unendlichen Listen natürlich zu einer Speicherbeschränkung kommen.

Auf der anderen Seite ist Corecursion dual zur Rekursion. Was bedeutet das? Genau wie die rekursiven Funktionen, die in ihren Begriffen ausgedrückt werden, werden kernkursive Variablen in ihren Begriffen ausgedrückt.

Dies lässt sich am besten am Beispiel ausdrücken.

Nehmen wir an, wir wollen eine Liste aller Primzahlen ...