Wie kommt es, dass unten auf der rechten Seite der Gleichung in Zeile könnte ein Symbol ‚fibs‘ verwenden, obwohl es noch nicht definiertem ist:Mit Symbol, bevor es definiertem wird
let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Der Punkt ist, dass die Definition von fibs
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
nicht ausgewertet wird, bis er irgendwo anders verwendet wird. Dann entfaltet sich die Definition mit dem bereits bekannten Teil. Wir beginnen mit fibs = 0 : 1 : ???. Dann, wenn das dritte Element jemals benötigt wird, wird die Definition einen Schritt weiter ausgewertet,
fibs = 0 : 1 : zipWith (+) (0 : 1 : ???) (tail (0 : 1 : ???))
= 0 : 1 : zipWith (+) (0 : 1 : ???) (1 : ???)
= 0 : 1 : (0 + 1) : zipWith (+) (1 : ???) (???)
aber dann der unbekannte Teil ??? ist teilweise bekannt geworden, bestimmt wurde, ??? = 1 : ???? zu sein, so kann die Entfaltung weitergehen,
= 0 : 1 : 1 : zipWith (+) (1 : 1 : ????) (1 : ????)
= 0 : 1 : 1 : 2 : zipWith (+) (1 : ????) (????)
-- now ???? is known to be 2:?????
= 0 : 1 : 1 : 2 : zipWith (+) (1 : 2 : ?????) (2 : ?????)
usw.
Danke, auf den ersten Blick sieht es komplizierter aus als die Funktion Rekursion. Gibt es Einschränkungen für die Syntax, die rekursiv Listen/Werte berechnet? Mit anderen Worten, aber nicht vorher, was ist erlaubt Syntax? – Trismegistos
Es gibt keine syntaktischen Einschränkungen, Sie verwenden nur den Wert, der in dem Ausdruck definiert ist, der definiert ist als "Wert = ein Ausdruck, der Wert verwendet". Der Punkt, auf den man achten muss, ist, ob die Berechnung beendet wird. Sie könnten beispielsweise versuchen, 'cycle xs = let result = result ++ xs in result' zu definieren. Aber wenn Sie versuchen, es auszuwerten, müssen Sie zuerst herausfinden, ob "result" nicht leer ist, um zu wissen, welche Gleichung für '(++)' verwendet werden soll. Sie betrachten also die Definition von 'result',' result = result ++ xs', um herauszufinden, ob 'result' nichtleer ist, müssen Sie herausfinden, ob' result' nichtleer ist ... –
Aber wenn Sie es definiert haben 'cycle xs = let result = xs ++ resultiere in result', du weißt bereits genug von' result', um nicht stecken zu bleiben, wenn die Notwendigkeit der Überprüfung von'result' bei der Berechnung von 'result' auftaucht (außer' xs' ist leer) , das würde dich in die Situation "let x = x in x" versetzen. Eine solche selbstreferenzierende Definition erfordert also, dass ein Teil des "Wertes" bestimmt werden kann, bevor er im definierenden Ausdruck untersucht wird, und der nächste benötigte Teil kann immer unter Verwendung dessen, was bereits bekannt ist, bestimmt werden. –
Es wird nicht wirklich versuchen, Rufen Sie fibs in Ihrer Definition, bis etwas anderes fibs später in Ihrem Programm verwendet, an dem Punkt fibs wurde vollständig definiert.
Sie können dies auch in den meisten anderen Sprachen tun:
int foo(int x)
{
if (x <= 0) return 0;
// will call foo when it gets there, at which point its been defined
foo(x - 1);
}
Ich verstehe Erholung in Imperativ-Sprachen und auch in Haskell, wenn es auf wenige Zeilen aufgeteilt ist. z. B. fib 0 = 0; fib 1 = 1; fib n = fib (n - 1) + fib (n - 2). Ich verstehe nicht, wie es im Beispiel verwendet wird, das ich in der Hauptfrage gegeben habe. – Trismegistos
@Trismegistos: Es ist genau das gleiche, Haskell muss diese Funktion nicht ausführen, bis sie aufgerufen wird. Wenn du 'fibs' irgendwo anders anrufst und innerhalb dieses Anrufs' fibs' erreicht, wird der Vorgang einfach erneut gestartet. Haskell muss es oder irgendetwas nicht aufrufen, während es definiert/analysiert wird. – GManNickG
Alle Haskell Bindungen sind rekursiv. Dies ist anders als in den meisten Sprachen, aber es funktioniert oft richtig aufgrund von Faulheit (Haskell Auswertung ist nicht-streng, im Gegensatz zu den meisten gängigen Sprachen). Newbies oft ausgelöst, wenn sie so etwas wie versuchen:
main = do
let a = 3
let a = 3 + a
print a
Da die zweite zu a tatsächlich ignoriert und Schatten die erste Bindung und definiert a in Bezug auf sich selbst, die eine Endlosschleife verursacht, wenn Sie versuchen, drucken Sie das Ergebnis der 3 + 3 + 3 + 3 + ...
Ein einfacheres Beispiel einer unendlichen Liste ist ones: eine unendliche Liste von 1 s
ones = 1 : ones
In diesem Fall bezieht sich diejenigen einfach selbst
_______
| |
v |
________ |
| ones | |
| 1 : ---|
--------
In Haskell, können Sie einen unendlichen Baum in die gleiche Weise erstellen, die Sie eine unendliche Liste erstellen:
data Tree a = Stub | Branch a (Tree a) (Tree a)
onesTree = Branch 1 onesTree onesTree
______ _______
| | | |
| v v |
| ____________ |
| | onesTree | |
|--- | 1 | ----|
------------
ich denke, die Die eigentliche Frage ist: Warum unterstützen andere Sprachen nicht so einfach rekursive Werte wie Haskell?
Nun, um das zu verstehen, ist es gut zu verstehen, wie faul Evaluation implementiert ist. Im Grunde werden unausgewertete Ausdrücke durch thunks dargestellt: eine Datenstruktur, die alle Informationen darstellt, die benötigt werden, um den Wert zu berechnen, wenn er tatsächlich benötigt wird.Wenn letzteres passiert (oder wie gesagt, wenn der Thunk erzwungen ist), wird der Code zur Berechnung des Wertes ausgeführt, und der Inhalt des Thunk wird durch das Ergebnis ersetzt, das Zeiger auf andere Thunks haben kann.
So beginnt fibs wie ein Thunk. Dieser Thunk enthält Zeiger auf den Code, der verwendet wird, um seinen Wert zu berechnen, und Zeiger auf die Thunks, die dieser Code als Argumente benötigt. Einer dieser letzteren Zeiger ist ein Zeiger auf fibs selbst.
@NiklasB. Ich weiß, was Rekursion ist, aber ich verstehe diesen speziellen Liner nicht. Siehe meinen Kommentar unter GManNickG Antwort. – Trismegistos
@NiklasB. In den meisten Sprachen springen Sie durch ein paar Ringe, um einen _value_ in seiner eigenen Definition zu verwenden. Nur wenige haben Faulheit eingebaut. –
@Daniel: Ja, stimmt, die meisten Sprachen unterstützen nur Rekursion für Funktionen, nicht für Listen. –