Warum foldRight und reduceRight sind NICHT tail rekursiv?

8

Warum Compiler Scala nicht übersetzt

%Vor%

zu Java entspricht

%Vor%

Die Frage ist: Warum foldLeft und redudeLeft sind rekursiv, aber ihre richtigen Gegenstücke nicht?

Hier sind Links, die sagen, dass Rechtshänder nicht tail rekursiv sind. Ich frage, warum es so ist.

Woher weißt du, wann man fold-left und wann man fold-right benutzt?

Auswirkungen von foldr vs. foldl (oder foldl ')

Ссылка

    
user482745 03.11.2010, 08:07
quelle

2 Antworten

9

(1, 2, 3, 4, 5, 6) ist ein 6-wertiges Tupel, das nicht foldRight , aber Array(1, 2, 3, 4, 5, 6) hat.

ArrayLike ist eine Merkmalunterklassierung von indexierten Sequenzen mit effizientem Elementzugriff, dh es wurden bestimmte Methoden optimiert, einschließlich zum Beispiel foldRight . Jedes Array wird implizit in eine Unterklasse des Attributs ArrayLike konvertiert. Von Scala Stamm:

%Vor%

Bytecode:

%Vor%

EDIT: Die Methode in Bytecode ist iterativ, was bedeutet, dass der Compiler eine Tail-Call-Optimierung angewendet haben muss.

Ohne einen effizienten Elementzugriff (dh eine effiziente apply -Methode) ist die beste generische Methode die Verwendung von Iteratoren und einer nicht-tail-rekursiven Funktion, um foldRight zu implementieren, oder das Umkehren der Sammlung durch Erstellen einer neuen und Ausführen von a foldLeft (letzteres ist zur Zeit getan). Bei allen Sequenzen mit effizientem Direktzugriff wird dieses Verhalten außer Kraft gesetzt und optimiert.

    
axel22 03.11.2010, 09:13
quelle
26

Es ist eine Frage, wie das Falten voranschreitet. Die Operation foldLeft arrangiert

%Vor%

als

%Vor%

(was 4 ist) während foldRight arrangiert

%Vor%

als

%Vor%

(was -8 ist).

Stellen Sie sich vor, Sie ziehen die Zahlen 1, 2 und 3 aus einer Tüte und machen die Rechnung auf Papier.

In dem Fall foldRight musst du es so machen:

  1. Ziehen Sie eine Zahl n aus der Tasche
  2. Schreibe " n -?" auf dem Papier
  3. Wenn noch Nummern in der Tasche sind, ziehen Sie ein anderes n aus der Tasche, sonst gehen Sie zu 6.
  4. Löschen Sie das Fragezeichen und ersetzen Sie es durch "( n -?)"
  5. Wiederholen Sie den Vorgang von 3.
  6. Lösche das Fragezeichen und ersetze es durch 10
  7. Führen Sie die Berechnung durch

Im Fall foldLeft können Sie dies folgendermaßen tun:

  1. Schreibe 10 auf das Papier
  2. Wenn noch Nummern in der Tasche sind, ziehen Sie ein anderes n aus der Tasche, sonst gehen Sie zu 5.
  3. Schreibe "- n " neben dem Ausdruck, den du bereits hast
  4. Wiederholen Sie von 2.
  5. Führen Sie die Berechnung durch

Aber Sie würden nicht, weil Sie es auch so machen können:

  1. Schreibe 10 auf das Papier
  2. Ziehen Sie eine Zahl n aus der Tasche
  3. Subtrahieren Sie n von dem Wert, den Sie haben, löschen Sie den Wert und notieren Sie stattdessen den neuen Wert
  4. Wiederholen Sie von 2.

Unabhängig davon, wie viele Zahlen in der Tasche enthalten sind, muss nur ein Wert auf Papier geschrieben sein. Tail Call Elimination (TCE) bedeutet, dass Sie anstelle einer großen Struktur von rekursiven Aufrufen auf dem Stack einen akkumulierten Wert ablegen und ersetzen können, während Sie fortfahren. (Das heißt, die rekursiv ausgedrückte Berechnung wird im Wesentlichen iterativ durchgeführt.)

Wie andere bereits festgestellt haben, ermöglicht eine Random-Access-Struktur wie ArrayLike , dass foldRight in eine foldLeft -Operation umgeordnet wird und somit für TCE infrage kommt. Die obige Beschreibung gilt für Fälle, in denen dies nicht möglich ist.

    
Peter Lewerin 03.11.2010 10:30
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset jquery dynamisch hinzugefügtes Kontrollkästchen, das nicht mit der Funktion change () funktioniert