Bieten Funktionen höherer Ordnung für die funktionale Programmierung mehr Leistung?

Question

Ich habe eine ähnliche Frage gestellt auf csthory.se.

Entsprechend Diese Antwort auf Stackoverflow Es gibt einen Algorithmus, der auf einer nicht-faulen reinen funktionalen Programmiersprache eine Komplexität von $ Omega (N log n) hat, während der gleiche Algorithmus bei der imperativen Programmierung $ omega (n) $ ist. Wenn der Algorithmus $ Omega (n) die FP -Sprache faul $ $ $ $ macht.

Gibt es eine äquivalente Beziehung, die eine FP -Sprache mit und ohne Funktionen höherer Ordnung vergleicht? Ist es immer noch vollständig? Wenn ja, macht der Mangel an höherer Ordnung bei FP die Sprache weniger "mächtig" oder effizient?

Answer 1

In einer funktionalen Programmiersprache, die leistungsstark genug ist (z. B. mit Datentypen zu implementieren Schließungen) Sie können alle Verwendungen von höherer Ordnung durch die Transformation von beseitigen Defunktionalisierung. Da diese Methode verwendet wird, um diese Art von Sprache zu kompilieren, können Sie vernünftigerweise davon ausgehen, dass dies keine Auswirkungen auf die Leistungen und das hat in dieser Einstellung höherer Ordnung macht die Sprache nicht weniger mächtig. Es wirkt sich jedoch auf das Schreiben von Code aus.

Wenn die Sprache jedoch nicht leistungsstark genug ist, bietet höhere Ordnung ausdrucksstarke Kraft. Betrachten Sie den Lambda-Calculus: Ohne eine Funktion höherer Ordnung kann es wirklich nichts tun, vor allem, weil die grundlegendsten Datentypen (Ganzzahlen, Booleane) mit Funktionen implementiert werden.

Zusammenfassend hängt es wirklich von der Sprache ab.

---

Oben ist meine Antwort. Im Folgenden ein Kommentar zu einer üblichen Annahme der imperativen Sprachen.

Über einen Algorithmus, der auf einer nicht-faulen funktionalen Programmiersprache eine $ omega (n log n) $ -Komplexität hat, während der gleiche Algorithmus in der imperativen Programmierung $ Omega (n) $ ist. Wenn der Algorithmus $ Omega (n) die FP -Sprache faul $ $ $ $ macht.

Ich würde gerne diese Referenz sehen. Die übliche Annahme ist, dass ein Zugriff auf eine Reihe von Länge $ n $ in einem RAM rechtzeitig $ O (1) $ und das Äquivalent in reinem FP in der Zeit $ O ( log n) $ ist. Das ist nicht ganz richtig: Die Zugriffszeit in einem RAM ist in $ o ( log m) $, wobei $ m $ die Größe des Speichers hat. Natürlich $ M≥n $. In der Praxis ist der Zugriff auf ein Element eines Arrays viel schneller. Ein Grund wäre, dass $ M $ begrenzt ist, aber ... also $ n $!

Bearbeiten: Vielen Dank für den Link (der Link für das Papier über Faulheit ist nicht verfügbar. hier ist noch einer). Wie in den Kommentaren und oben in meiner Antwort veröffentlicht, ist das Modell des RAM für reine FP ein wenig unfair, indem es $ O (1) $-Zeitangebote bereitstellt, auch wenn die Größe einer Adresse nicht begrenzt ist. Ich muss noch verstehen, wie der faule Trick funktioniert, aber ich denke, es ist wichtig zu beachten, dass dies nur für dieses spezielle Problem ist.

Answer 2

Es hängt davon ab, was Sie mit Ausdruckskraft meinen.

Hier ist ein Argument, dass höherer Ordnung etwas hinzufügt: Mit Sprachen erster Ordnung reicht die primitive Rekursion nicht aus, um das auszudrücken Ackermann -Funktion. In Gegenwart von Funktionen höherer Ordnung reicht jedoch eine primitive Rekursion aus:

$$ begin {array} {lcl} textit {ackermann} 0 & = & lambda x. x+1 textit {ackermann} (m+1) & = & textit {iter} ( textit {ackermann} m) textit {iter} f 0 & = & F 1 textit {iter} f (n+1) & = & f ( textit {iter} f n) end {Array} $$

Dies definiert die Ackermann -Funktion nur unter Verwendung der primitiven Rekursion.

Beachten Sie, dass $ textit {iter} $ in der herkömmlichen Rekursionstheorie nicht definierbar ist, da $ textit {iter} $ eine höhere Ordnung ist. In der konventionellen Rekursionstheorie haben alle definierbaren Funktionen $ mathbb {n}^k rightarrow mathbb {n} $ für einige $ k $, während $ textit {iter} $ type $ ( mathbb {n} rightarrow hat mathbb {n}) rightarrow ( mathbb {n} rightarrow mathbb {n}) $.