Algorytmy wyższego rzędu

Większość dobrze znanych algorytmów jest pierwszego rzędu, w tym sensie, że ich dane wejściowe i wyjściowe są danymi „prostymi”. Niektóre są drugiego rzędu w trywialny sposób, na przykład sortowanie, tablice skrótów lub funkcje mapowania i składania: są one parametryzowane przez funkcję, ale tak naprawdę nie robią z nią nic ciekawego oprócz wywoływania jej na innych danych wejściowych.

Niektóre są również drugiego rzędu, ale nieco bardziej interesujące:

• Palce parametryzowane przez monoidy
• Dzielenie palca na monotonne orzeczenie
• Algorytmy sumy prefiksów, ponownie zwykle parametryzowane przez monoid lub predykat itp.

Wreszcie, niektóre są „naprawdę” wyższego rzędu w sensie, który jest dla mnie najbardziej interesujący:

• Kombinator Y.
• Listy różnic

Czy istnieją inne nietrywialne algorytmy wyższego rzędu?

Próbując wyjaśnić moje pytanie, pod „nietrywialnym wyższym rzędem” mam na myśli „krytyczne wykorzystanie udogodnień formalizmu obliczeniowego w interfejsie i / lub implementacji algorytmu”

Na stronie http://math.andrej.com/ istnieje wiele funkcji wyższego rzędu , na przykład w poście o podwójnych wykładniczych pojawia się następujący typ Haskella (z rozwiniętymi synonimami typu):

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

Możesz także dobrze się bawić dzięki postowi Monada Haskella do nieskończonego wyszukiwania w ograniczonym czasie - na przykład:

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

Myślę, że typ bigUnion to 4. lub 5. zamówienie!

istnieje szereg algorytmów, które są „naprawdę drugiego rzędu”, chociaż zwykle nie są wyraźnie opisane w tych terminach. Ilekroć mamy subliniowe algorytmy czasowe, niejawny jest pewien rodzaj wyroczni dostępu do danych wejściowych, tj. Naprawdę traktowanie danych wejściowych jako funkcji.

Przykłady:

(1) Algorytmy elipsoidy podczas pracy z „wyrocznią separacyjną” (np. Http://math.mit.edu/~vempala/18.433/L18.pdf )

(2) Submodular minimalizacji funkcji (np http://people.commerce.ubc.ca/faculty/mccormick/sfmchap8a.pdf )

(3) Cała dziedzina testowania właściwości jest naprawdę w tej formie ( http://www.wisdom.weizmann.ac.il/~oded/test.html )

(4) Aukcje kombinatoryczne w modelu zapytania (np. Http://pluto.huji.ac.il/~blumrosen/papers/iter.pdf )

Istnieje inna odpowiedź na to pytanie: nie ma żadnych. Mówiąc dokładniej, każdy taki (możliwy do wdrożenia!) Algorytm wyższego rzędu jest mechanicznie równoważny algorytmowi pierwszego rzędu, wykorzystując defunkcjonalizację .

Pozwólcie, że uściślę: chociaż rzeczywiście istnieją rzeczywiste algorytmy wyższego rzędu, w praktyce zawsze można przepisać każdą instancję jako program czysto pierwszego rzędu. Innymi słowy, nie ma nasyconych programów wyższego rzędu - zasadniczo dlatego, że wejścia / wyjścia programów są łańcuchami bitów. [Tak, te ciągi bitów mogą reprezentować funkcje, ale o to właśnie chodzi: oni reprezentują funkcje są nie funkcjonuje].

Odpowiedzi już podane są doskonałe, a mojej odpowiedzi nie należy uważać za sprzeczną z nimi. Należy to uznać za odpowiedź na pytanie w nieco większym kontekście (kompletne programy zamiast samodzielnych algorytmów). Ta zmiana kontekstu zmienia radykalnie odpowiedź. Celem mojej odpowiedzi jest przypomnienie ludziom o tym, o czym zbyt łatwo zapomnieć.

W bibliotekach kombinatora parsera kolejność funkcji jest na ogół dość wysoka. Sprawdź nawet funkcje wyższego rzędu do analizowania lub dlaczego ktoś miałby kiedykolwiek chcieć użyć funkcji szóstego rzędu? autor: Chris Okasaki. Journal of Functional Programming , 8 (2): 195-199, marzec 1998.

Analiza obliczalna charakteryzuje programowo liczby rzeczywiste, ponieważ liczby rzeczywiste zawierają nieograniczoną ilość informacji, a zatem operacje na liczbach rzeczywistych są wyższego rzędu w sensie pytań. Zazwyczaj liczby rzeczywiste są przedstawiane przy użyciu widoku topologicznego nieskończonego strumienia bitów, przestrzeni Cantora, interesując się szerszym obszarem obliczeniowej topologii.

Klaus Weihrach mówił o tym jako o hierarchii efektywności typu drugiego obliczalnej topologii. Więcej informacji na ten temat można znaleźć w Weihrach & Grubba, 2009, Elementary Computable Topology oraz na stronie badawczej John Tucker, Computation with Topological Data . Wspominam o stronie Tuckera w moim pytaniu Zastosowania przestrzeni kantora .

Moduł ciągłości funkcjonalna jest na mapie m, który przyjmuje wartości (ciąg dalszy) funkcjonalny F : (nat -> nat) -> nati wysyła liczbę ktak, że F f = F ggdy f i = g idla wszystkich i < k. Istnieją algorytmy obliczania modułu ciągłości (niezbyt wydajne), dzięki czemu jest to przykład algorytmu trzeciego rzędu.

Aby uzupełnić odpowiedź Noama , istnieje również kilka sytuacji, w których ważne jest, aby wynik był (wyraźną reprezentacją) funkcji.

$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$

W algorytmach graficznych wierzchołki i krawędzie są zwykle uważane za zwykłe dane, ale w rzeczywistości można je produktywnie uogólnić, aby były generowane programowo na żądanie.

Podczas mojego doktoratu (z chemii obliczeniowej) zaimplementowałem wiele algorytmów graficznych w formie wyższego rzędu, aby zastosować je do analizy ukrytych wykresów, głównie dlatego, że moje rzeczywiste wykresy były nieskończone, więc nie mogłem sobie pozwolić na ich jawne przechowywanie! W szczególności badałem topologię materiałów amorficznych przedstawionych jako trójwymiarowe przechylenie komórek elementarnych (superkomórek).

Na przykład możesz napisać funkcję obliczającą n-najbliższą sąsiednią powłokę wierzchołka pochodzenia w inastępujący sposób:

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))

gdzie neighborsjest funkcją, która zwraca zestaw sąsiednich wierzchołków do danego wierzchołka.

Na przykład kwadratowa sieć 2D:

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

Inne interesujące algorytmy w tym kontekście obejmują najkrótszą statystykę pierścienia Franzblau.