Algorithmen höherer Ordnung

Die meisten bekannten Algorithmen sind in dem Sinne erster Ordnung, dass ihre Eingabe und Ausgabe "reine" Daten sind. Einige sind in trivialer Weise von zweiter Ordnung, zum Beispiel Sortierung, Hashtabellen oder Map- und Fold-Funktionen: Sie werden durch eine Funktion parametrisiert, aber sie tun nichts wirklich Interessantes damit, außer sie für Teile anderer Eingabedaten aufzurufen.

Einige sind auch zweiter Ordnung, aber etwas interessanter:

• Von Monoiden parametrisierte Fingerbäume
• Aufteilen eines Fingerabdrucks auf ein eintöniges Prädikat
• Präfixsummenalgorithmen, die wiederum normalerweise durch ein Monoid oder ein Prädikat usw. parametrisiert werden.

Schließlich sind einige in dem für mich interessantesten Sinne "wirklich" übergeordnet:

• Der Y-Kombinator
• Differenzlisten

Gibt es noch andere nichttriviale Algorithmen höherer Ordnung?

In dem Versuch, meine Frage zu klären, meine ich unter "nichttrivialer höherer Ordnung" "die kritische Verwendung von Einrichtungen höherer Ordnung des Computerformalismus in der Schnittstelle und / oder Implementierung des Algorithmus".

Unter http://math.andrej.com/ gibt es viele Funktionen höherer Ordnung. In dem Beitrag über doppelte Exponentiale wird beispielsweise der folgende Haskell-Typ angezeigt (mit erweiterten Synonymen):

shift :: Bool -> ((Int -> Bool) -> Bool) -> ((Int -> Bool) -> Bool)

Sie können auch viel Spaß mit dem Beitrag A Haskell Monad for Infinite Search in Finite Time haben - zum Beispiel:

newtype S a = S ((a -> Bool) -> a)
bigUnion :: S (S a) -> S a

Ich denke, die Art von bigUnion ist 4. oder 5. Ordnung!

Es gibt eine Reihe von Algorithmen, die "wirklich 2. Ordnung" sind, obwohl sie normalerweise nicht explizit in diesen Begriffen beschrieben werden. Immer wenn wir sublineare Zeitalgorithmen haben, ist implizit eine Art Orakelzugriff auf die Eingabe, dh die Eingabe wird wirklich als Funktion behandelt.

Beispiele:

(1) Die Ellipsoid-Algorithmen beim Arbeiten mit einem "Trennungsorakel" (zB http://math.mit.edu/~vempala/18.433/L18.pdf )

(2) Submodulare Funktionsminimierung (zB http://people.commerce.ubc.ca/faculty/mccormick/sfmchap8a.pdf )

(3) Der gesamte Bereich der Eigenschaftsprüfung ist wirklich von dieser Form ( http://www.wisdom.weizmann.ac.il/~oded/test.html ).

(4) Kombinatorische Auktionen im Abfragemodell (zB http://pluto.huji.ac.il/~blumrosen/papers/iter.pdf )

Es gibt eine andere Antwort auf diese Frage: Es gibt keine. Insbesondere ist ein solcher (implementierbarer!) Algorithmus höherer Ordnung unter Verwendung von Defunktionalisierung mechanisch äquivalent zu einem Algorithmus erster Ordnung .

Lassen Sie mich genauer sein: Zwar gibt es tatsächlich Algorithmen höherer Ordnung, in der Praxis ist es jedoch immer möglich, jede Instanz als reines Programm erster Ordnung neu zu schreiben . Mit anderen Worten, es gibt keine gesättigten Programme höherer Ordnung - im Wesentlichen, weil die Eingabe / Ausgabe von Programmen Bitfolgen sind. [Ja, diese Bitfolgen können Funktionen darstellen, aber das ist der Punkt: Sie stellen Funktionen dar, sie sind keine Funktionen].

Die bereits gegebenen Antworten sind ausgezeichnet, und meine Antwort sollte nicht als widersprüchlich angesehen werden. Es sollte als Beantwortung der Frage aus einem etwas größeren Kontext betrachtet werden (vollständige Programme anstelle von eigenständigen Algorithmen). Und dieser Kontextwechsel verändert die Antwort ganz radikal. Der Punkt meiner Antwort ist, die Menschen daran zu erinnern, was allzu leicht zu vergessen ist.

In Parser-Combinator-Bibliotheken ist die Reihenfolge der Funktion im Allgemeinen ziemlich hoch. Schauen Sie sich Funktionen höherer Ordnung zum Parsen an oder warum sollte jemand jemals eine Funktion sechster Ordnung verwenden wollen? von Chris Okasaki. Journal of Functional Programming , 8 (2): 195-199, März 1998.

Eine berechenbare Analyse charakterisiert reelle Zahlen programmatisch, da reelle Zahlen eine unbegrenzte Menge an Informationen enthalten und Operationen mit reellen Zahlen daher im Sinne der Fragen übergeordnet sind. Typischerweise werden reelle Zahlen unter Verwendung einer topologischen Ansicht des unendlichen Bitstroms, des Cantor-Raums, dargestellt, was das breitere Feld der berechenbaren Topologie interessiert.

Klaus Weihrach hat dies als Typ-Zwei-Hierarchie der Effektivität berechenbarer Topologien bezeichnet. Weitere Informationen finden Sie in Weihrach & Grubba, 2009, Elementary Computable Topology , und auf der Forschungsseite von John Tucker, Computing with Topological Data . Ich erwähne Tuckers Seite in meiner Frage, Applications of Cantor Space .

Ein Kontinuitätsmodul ist eine Karte, mdie eine (kontinuierliche) Funktion akzeptiert F : (nat -> nat) -> natund eine Zahl ausgibt k, die F f = F gimmer f i = g ifür alle gilt i < k. Es gibt Algorithmen zur Berechnung des Kontinuitätsmoduls (nicht sehr effiziente), so dass es eine Instanz eines Algorithmus 3. Ordnung ist.

Um Noams Antwort zu ergänzen , gibt es auch einige Situationen, in denen es wichtig ist, dass die Ausgabe eine Funktion ist (eine explizite Darstellung davon).

$C: \\{0,1\\}^n \rightarrow \\{0,1\\}^m$$A$ $(\alpha,L,\epsilon)$$C$$n$$A$$M_1,\dots,M_L$

$\begin{align}\forall w \in \\{0,1\\}^m, Pr_A [&\forall m,~(Ag(C(m),w) \geq \alpha \Rightarrow \\\ &\exists i \in [L],~\forall j \in [n],~Pr_{M_i}[M_i(j) = m_j] \geq 1-\epsilon)] \geq 2/3\end{align}$

$Ag$$A$$2/3$$\epsilon$$m$$m$$\alpha$

In Grafikalgorithmen werden Scheitelpunkte und Kanten normalerweise als reine Daten betrachtet, aber sie können tatsächlich produktiv verallgemeinert werden, so dass sie bei Bedarf programmgesteuert generiert werden.

Während meiner Doktorarbeit (in Computerchemie) habe ich viele Graphenalgorithmen in höherer Ordnung implementiert, um sie auf die Analyse impliziter Graphen anzuwenden, hauptsächlich, weil meine tatsächlichen Graphen unendlich waren und ich es mir nicht leisten konnte, sie explizit zu speichern! Insbesondere untersuchte ich die Topologie amorpher Materialien, die als 3D-Kacheln von Elementarzellen (Superzellen) dargestellt werden.

Beispielsweise können Sie eine Funktion schreiben, um die n-nächstgelegene Nachbarshell eines Ursprungsscheitelpunkts iwie folgt zu berechnen :

nth i 0 = {i}
nth i 1 = neighbors i
nth i n = diff (diff (fold union empty (map neighbors (nth i (n-1)))) (nth i (n-1))) (nth i (n-2))

Dabei neighborshandelt es sich um eine Funktion, die die Menge benachbarter Scheitelpunkte zum angegebenen Scheitelpunkt zurückgibt.

Zum Beispiel das 2D-Quadratgitter:

neighbors (x, y) = {(x-1, y), (x+1, y), (x, y-1), (x, y+1)}

Weitere interessante Algorithmen in diesem Zusammenhang sind Franzblaus Shortest-Path-Ring-Statistiken.