Algorithmen höherer Ordnung

35

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".

jkff
quelle
3
Ich habe einmal etwas Ähnliches gefragt. Einige Antworten hier: caml.inria.fr/pub/ml-archives/caml-list/2004/09/…
Radu GRIGore
Sprechen Sie über Algorithmen, die Algorithmen verwenden und / oder Algorithmen zurückgeben?
Pratik Deoghare

Antworten:

13

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!

yatima2975
quelle
22

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 )

Noam
quelle
15

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.

Jacques Carette
quelle
Ich stimme zu, dass jeder Algorithmus höherer Ordnung einem Algorithmus erster Ordnung mit derselben externen Spezifikation entspricht, aber dies sollte uns nicht davon abhalten, über ihre internen Eigenschaften zu streiten. Es gibt keinen Unterschied zwischen etwas darstellen und etwas sein.
jkff
1
@jkff: Ich stimme Ihrem ersten Punkt zu - wir sollten auf jeden Fall über diese internen Eigenschaften sprechen. Ich stimme dem zweiten Punkt nachdrücklich nicht zu: Sie behaupten irgendwie, dass Erweiterungen und Intensionen „gleich“ sind, was einfach offensichtlich falsch ist. [Erinnert mich an das Matisse-Gemälde 'Das ist keine Pfeife']
Jacques Carette
Ach ja, "Der Verrat der Eta-Bekehrung". (\\() -> "Ceci n'est pas une fonction") ()
CA McCann
Ich behaupte, wenn zwei Dinge gleichwertig sind (indem man sich gegenseitig repräsentiert), kann man die Existenz von einem von ihnen nicht leugnen :)
jkff
@jkff: schwer zu widersprechen!
Jacques Carette
13

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.

Dave Clarke
quelle
Dies ist ein großartiges Papier, aber nicht genau das, wonach ich suche. Obwohl die Kombinatoren höherer Ordnung sind, sind sie sehr einfach und unabhängig, und jeder einzelne von ihnen würde kaum als nicht-triviale Algorithmus- / Datenstruktur gelten (möglicherweise würden Kombinator-Parser dies jedoch selbst tun). Im Gegenteil, der Y-Kombinator ist ein höchst nicht-trivialer Algorithmus zum Auffinden eines festen Punkts, und Differenzlisten sind eine clevere Datenstruktur, die vollständig aus Funktionen höherer Ordnung aufgebaut ist. (Ich untergrabe Ihre Antwort nicht und versuche nur, meine Frage zu klären)
jkff
13

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 .

Charles Stewart
quelle
Und dies erstreckt sich ganz natürlich auf berechenbare mathematische Objekte im Allgemeinen: andere berechenbare Zahlen (nicht unbedingt reelle), berechenbare Elemente unendlicher Gruppen (Ringe, Algebren, ...), berechenbare Punkte in Räumen usw. In all diesen Fällen ist der Algorithmus Die Theorie bezieht sich auf das Extrahieren von Informationen aus der funktionalen Repräsentation (wie das mathematische Objekt berechnet wird) und nicht aus dem Objekt selbst.
ex0du5,
13

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.

Andrej Bauer
quelle
9

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,1n0,1mEIN (α,L,ϵ)CnEINM1,,ML

w0,1m,PrEIN[m, (EING(C(m),w)α ich[L], j[n], PrMich[Mich(j)=mj]1-ϵ)]2/3

EINGEIN2/3ϵmmα

Arnab
quelle
5

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.

Jon Harrop
quelle
Dies bringt mich zu einer Frage, die ich einmal hatte. Wenn es programmatische Möglichkeiten gibt, Graphen auf diese Weise zu definieren, gibt es eine Möglichkeit, einen selbstreferenziellen paradoxen Graphen zu definieren?
Suresh Venkat
1
{x:xx}{x:xx}
Sicher. Aber ist das ein selbstreferenzieller Graph ?
Suresh Venkat
@Suresh: Es ist ein Graph, der in einer funktionalen Sprache in dem Sinne definiert ist, dass es eine Art Uvon Eckpunkten und eine Funktion U -> U -> Boolvon Kanten gibt.
SDCVVC