Algoritmos de orden superior

35

La mayoría de los algoritmos conocidos son de primer orden, en el sentido de que su entrada y salida son datos "simples". Algunos son de segundo orden de una manera trivial, por ejemplo, la clasificación, las tablas hash o las funciones de mapa y plegado: están parametrizados por una función, pero en realidad no hacen nada interesante excepto invocarlo en otros datos de entrada.

Algunos también son de segundo orden pero algo más interesantes:

  • Yemas de los dedos parametrizadas por monoides
  • Dividir un dedo en un predicado monótono
  • Algoritmos de suma de prefijos, nuevamente parametrizados por un monoide o un predicado, etc.

Finalmente, algunos son "verdaderamente" de orden superior en el sentido que es más interesante para mí:

  • El combinador Y
  • Listas de diferencias

¿Existen otros algoritmos no triviales de orden superior?

En un intento por aclarar mi pregunta, bajo "orden superior no trivial" me refiero a "usar facilidades de orden superior del formalismo computacional de manera crítica en la interfaz y / o implementación del algoritmo"

jkff
fuente
3
Pregunté algo similar una vez. Algunas respuestas aquí: caml.inria.fr/pub/ml-archives/caml-list/2004/09/…
Radu GRIGore
¿Están hablando de algoritmos que toman algoritmos y / o retornan algoritmos?
Pratik Deoghare

Respuestas:

13

Hay muchas funciones de orden superior en http://math.andrej.com/ , por ejemplo, en la publicación sobre exponenciales dobles , aparece el siguiente tipo de Haskell (con los sinónimos de tipo expandidos):

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

También puede divertirse mucho con la publicación A Haskell Monad for Infinite Search in Finite Time , por ejemplo:

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

¡Supongo que el tipo de bigUnion es de 4to o 5to orden!

yatima2975
fuente
22

hay un montón de algoritmos que son "realmente de segundo orden" aunque generalmente no se describen explícitamente en estos términos. Siempre que tenemos algoritmos de tiempo sub-lineales, implícito es algún tipo de acceso oráculo a la entrada, es decir, realmente trata la entrada como una función.

Ejemplos:

(1) Los algoritmos elipsoides cuando se trabaja con un "oráculo de separación" (por ejemplo, http://math.mit.edu/~vempala/18.433/L18.pdf )

(2) Minimización de la función submodular (por ejemplo, http://people.commerce.ubc.ca/faculty/mccormick/sfmchap8a.pdf )

(3) Todo el campo de las pruebas de propiedad es realmente de esta forma ( http://www.wisdom.weizmann.ac.il/~oded/test.html )

(4) Subastas combinadas en el modelo de consulta (por ejemplo, http://pluto.huji.ac.il/~blumrosen/papers/iter.pdf )

Noam
fuente
15

Hay otra respuesta a esta pregunta: no hay ninguna. Más específicamente, cualquier algoritmo de orden superior de este tipo (¡implementable!) Es mecánicamente equivalente a un algoritmo de primer orden, que utiliza la desfuncionalización .

Permítanme ser más preciso: si bien existen algoritmos reales de orden superior, en la práctica siempre es posible reescribir cada instancia como un programa puramente de primer orden. En otras palabras, no hay programas saturados de orden superior, esencialmente porque la entrada / salida de los programas son cadenas de bits. [Sí, esas cadenas de bits pueden representar funciones, pero ese es el punto: que representan funciones, que son no funciona].

Las respuestas ya dadas son excelentes, y mi respuesta no debe considerarse como una contradicción. Debe considerarse como una respuesta a la pregunta desde un contexto un poco más amplio (programas completos en lugar de algoritmos independientes). Y este cambio de contexto cambia la respuesta de manera radical. El punto de mi respuesta es recordarle a la gente esto, que es demasiado fácil de olvidar.

Jacques Carette
fuente
Estoy de acuerdo en que cualquier algoritmo de orden superior es equivalente a un algoritmo de primer orden con la misma especificación externa, pero esto no debería impedirnos discutir sobre sus propiedades internas. No hay diferencia entre representar algo y ser algo.
jkff
1
@jkff: Estoy de acuerdo con su primer punto, definitivamente deberíamos discutir estas propiedades internas. Estoy totalmente en desacuerdo con el segundo punto: de alguna manera estás afirmando que las extensiones e intensiones son 'lo mismo', lo cual es claramente falso. [Me recuerda a la pintura de Matisse 'esto no es una pipa']
Jacques Carette
Ah, sí, "La traición de la conversión de Eta". (\\() -> "Ceci n'est pas une fonction") ()
CA McCann
Estoy afirmando que si dos cosas son equivalentes (al representarse entre sí), no puede negar la existencia de una de ellas :)
jkff
@jkff: es difícil no estar de acuerdo con eso!
Jacques Carette
13

En las bibliotecas de combinador de analizador, el orden de la función es generalmente bastante alto. Echa un vistazo a las funciones de orden aún más alto para analizar o ¿Por qué alguien querría usar una función de sexto orden? por Chris Okasaki. Journal of Functional Programming , 8 (2): 195-199, marzo de 1998.

Dave Clarke
fuente
Este es un gran trabajo, pero no es exactamente lo que estoy buscando. Aunque los combinadores son de orden superior, son muy simples e independientes, y cualquiera de ellos difícilmente se consideraría como un algoritmo / estructura de datos no trivial (sin embargo, quizás los analizadores combinados sí lo harían). Por el contrario, el combinador Y es un algoritmo altamente no trivial para encontrar un punto fijo, y las listas de diferencias son una estructura de datos inteligente construida completamente a partir de funciones de orden superior. (No estoy socavando su respuesta, solo estoy tratando de aclarar mi pregunta)
jkff
13

El análisis computable caracteriza los números reales mediante programación, ya que los números reales contienen una cantidad ilimitada de información, por lo que las operaciones con números reales son de orden superior en el sentido de las preguntas. Por lo general, los números reales se presentan utilizando una vista topológica en el flujo infinito de bits, el espacio de Cantor, lo que presta interés al campo más amplio de la topología computable.

Klaus Weihrach ha hablado de esto como la Jerarquía de efectividad de tipo dos de la topología computable. Para obtener más información al respecto, consulte Weihrach & Grubba, 2009, Topología computable elemental , y la página de investigación de John Tucker, Computación con datos topológicos . Menciono la página de Tucker en mi pregunta, Aplicaciones de Cantor Space .

Charles Stewart
fuente
Y esto se extiende de forma bastante natural a los objetos matemáticos computables en general: otros números computables (no necesariamente reales), elementos computables de grupos infinitos (anillos, álgebras, ...), puntos computables en espacios, etc. En todos estos casos, el algoritmo La teoría se refiere a la extracción de información de la representación funcional (de cómo calcular el objeto matemático), y no del objeto en sí.
ex0du5
13

Un módulo de continuidad funcional es un mapa mque acepta un funcional (continuo) F : (nat -> nat) -> naty genera un número ktal que F f = F gsiempre que sea f i = g ipara todos i < k. Existen algoritmos para calcular el módulo de continuidad (no muy eficientes), lo que lo convierte en una instancia de un algoritmo de tercer orden.

Andrej Bauer
fuente
9

Para complementar la respuesta de Noam , también hay varias situaciones en las que es importante que la salida sea ​​(una representación explícita de) una función.

Un ejemplo interesante es la definición de un código decodificable por lista. Deje que sea ​​un código. Decimos que un algoritmo probabilístico lista-decodifica si en la entrada , genera máquinas probabilísticas manera que:C:0,1n0,1mA (α,L,ϵ)CnAM1,,ML

w0,1m,PrA[m, (Ag(C(m),w)α i[L], j[n], PrMi[Mi(j)=mj]1ϵ)]2/3

Aquí, denota la fracción de coordenadas con las que las dos cadenas están de acuerdo. En otras palabras, para cada palabra recibida, la salida de debe contener, con una probabilidad de al menos , una máquina que aproxima a para cada mensaje cuya codificación concuerda con al menos fracción de las coordenadas de la palabra recibidaA 2 / 3 ε m m αAgA2/3ϵmmα

arnab
fuente
5

En los algoritmos gráficos, los vértices y los bordes generalmente se consideran datos simples, pero en realidad pueden generalizarse productivamente para que se generen mediante programación a pedido.

Durante mi doctorado (en química computacional) implementé muchos algoritmos gráficos en forma de orden superior para aplicarlos al análisis de gráficos implícitos, principalmente porque mis gráficos reales eran infinitos, ¡así que no podía permitirme almacenarlos explícitamente! Específicamente, estaba estudiando la topología de materiales amorfos representados como inclinaciones 3D de células unitarias (supercélulas).

Por ejemplo, puede escribir una función para calcular el enésimo vecino más cercano de un vértice de origen icomo este:

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

donde neighborses una función que devuelve el conjunto de vértices vecinos al vértice dado.

Por ejemplo, la red cuadrada 2D:

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

Otros algoritmos interesantes en este contexto incluyen las estadísticas de anillos de ruta más cortos de Franzblau.

Jon Harrop
fuente
Esto me lleva a una pregunta que tuve una vez. Si hay formas programáticas de definir gráficos de esta manera, ¿hay alguna manera de definir un gráfico paradójico autorreferencial?
Suresh Venkat
1
@Suresh: es posible replicar la paradoja de Russell en un lenguaje funcional; evaluar se atascará en un bucle infinito. Ver, por ejemplo, blog.sigfpe.com/2008/01/type-that-should-not-be.html{x:xx}{x:xx}
sdcvvc
Seguro. ¿Pero es eso un gráfico autorreferencial ?
Suresh Venkat
@Suresh: es un gráfico definido en un lenguaje funcional en el sentido de que hay un tipo Ude vértices y una función U -> U -> Boolde bordes.
sdcvvc