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”
Odpowiedzi:
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):
Możesz także dobrze się bawić dzięki postowi Monada Haskella do nieskończonego wyszukiwania w ograniczonym czasie - na przykład:
Myślę, że typ bigUnion to 4. lub 5. zamówienie!
źródło
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 )
źródło
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ć.
źródło
(\\() -> "Ceci n'est pas une fonction") ()
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.
źródło
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 .
źródło
Moduł ciągłości funkcjonalna jest na mapie
m
, który przyjmuje wartości (ciąg dalszy) funkcjonalnyF : (nat -> nat) -> nat
i wysyła liczbęk
tak, żeF f = F g
gdyf i = g i
dla wszystkichi < k
. Istnieją algorytmy obliczania modułu ciągłości (niezbyt wydajne), dzięki czemu jest to przykład algorytmu trzeciego rzędu.źródło
Aby uzupełnić odpowiedź Noama , istnieje również kilka sytuacji, w których ważne jest, aby wynik był (wyraźną reprezentacją) funkcji.
źródło
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
i
następujący sposób:gdzie
neighbors
jest funkcją, która zwraca zestaw sąsiednich wierzchołków do danego wierzchołka.Na przykład kwadratowa sieć 2D:
Inne interesujące algorytmy w tym kontekście obejmują najkrótszą statystykę pierścienia Franzblau.
źródło
U
wierzchołków i funkcjaU -> U -> Bool
krawędzi.