Algorytmy wyższego rzędu

35

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”

jkff
źródło
3
Raz zapytałem o coś podobnego. Kilka odpowiedzi tutaj: caml.inria.fr/pub/ml-archives/caml-list/2004/09/…
Radu GRIGore
Czy mówicie o algorytmach, które przyjmują algorytmy i / lub zwracają algorytmy?
Pratik Deoghare

Odpowiedzi:

13

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!

yatima2975
źródło
22

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 )

Noam
źródło
15

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

Jacques Carette
źródło
Zgadzam się, że każdy algorytm wyższego rzędu jest równoważny niektórym algorytmom pierwszego rzędu o tej samej specyfikacji zewnętrznej, ale nie powinno to uniemożliwiać nam kłótni o ich właściwości wewnętrzne. Nie ma różnicy między reprezentowaniem czegoś a byciem czymś.
jkff
1
@jkff: Zgadzam się z twoim pierwszym punktem - zdecydowanie powinniśmy omówić te wewnętrzne właściwości. Z całą stanowczością nie zgadzam się z drugą kwestią: jakoś twierdzisz, że rozszerzenia i zamiary są „takie same”, co jest po prostu ewidentnie fałszywe. [Przypomina mi obraz Matisse'a „to nie jest fajka”]
Jacques Carette
Ach, tak, „The Treachery of Eta Conversion”. (\\() -> "Ceci n'est pas une fonction") ()
CA McCann,
Twierdzę, że jeśli dwie rzeczy są równoważne (reprezentując się nawzajem), nie można zaprzeczyć istnieniu jednej z nich :)
jkff 1'10
@jkff: trudno się z tym nie zgodzić!
Jacques Carette,
13

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.

Dave Clarke
źródło
To świetny papier, ale nie do końca to, czego szukam. Chociaż kombinatory są wyższego rzędu, są bardzo proste i niezależne, a żaden z nich z trudem liczyłby się jako nietrywialny algorytm / struktura danych (jednak być może same parsery kombinatora). Wręcz przeciwnie, kombinator Y jest wysoce nietrywialnym algorytmem znajdowania stałego punktu, a listy różnic są sprytną strukturą danych zbudowaną w całości z funkcji wyższego rzędu. (Nie podważam twojej odpowiedzi, po prostu próbuję wyjaśnić moje pytanie)
jkff
13

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 .

Charles Stewart
źródło
Rozciąga się to całkiem naturalnie na ogólnie obliczalnych obiektach matematycznych: innych liczbach obliczalnych (niekoniecznie rzeczywistych), elementach obliczeniowych nieskończonych grup (pierścienie, algebry, ...), punktach obliczeniowych w przestrzeni itp. We wszystkich takich przypadkach algorytmika teoria dotyczy wydobywania informacji z reprezentacji funkcjonalnej (jak obliczyć obiekt matematyczny), a nie z samego obiektu.
ex0du5
13

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.

Andrej Bauer
źródło
9

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,1n0,1mA (α,L.,ϵ)donZAM.1,,M.L.

w0,1m,P.rZA[m, (ZAsol(do(m),w)α ja[L.], jot[n], P.rM.ja[M.ja(jot)=mjot]1-ϵ)]2)/3)

ZAsolZA2)/3)ϵmmα

arnab
źródło
5

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.

Jon Harrop
źródło
To prowadzi mnie do pytania, które kiedyś miałem. Jeśli istnieją programowe sposoby definiowania wykresów w ten sposób, czy istnieje sposób zdefiniowania samoreferencyjnego wykresu paradoksalnego?
Suresh Venkat
1
{x:xx}{x:xx}
Pewnie. Ale czy to wykres autoreferencyjny ?
Suresh Venkat,
@Suresh: Jest to wykres zdefiniowany w języku funkcjonalnym w tym sensie, że istnieje rodzaj Uwierzchołków i funkcja U -> U -> Boolkrawędzi.
sdcvvc