Algoritmos de ordem superior

35

A maioria dos algoritmos conhecidos é de primeira ordem, no sentido de que sua entrada e saída são dados "simples". Alguns são de segunda ordem de uma maneira trivial, por exemplo, classificação, hashtables ou funções map e fold: são parametrizadas por uma função, mas na verdade não fazem nada de interessante, exceto invocá-la em partes de outros dados de entrada.

Alguns também são de segunda ordem, mas um pouco mais interessantes:

  • Fingertrees parametrizados por monoides
  • Divisão de uma fingertree em um predicado monótono
  • Algoritmos de soma de prefixos, novamente normalmente parametrizados por um monóide ou predicado etc.

Finalmente, alguns são "verdadeiramente" de ordem superior, no sentido mais interessante para mim:

  • O combinador Y
  • Listas de diferenças

Existem outros algoritmos não triviais de ordem superior?

Na tentativa de esclarecer minha pergunta, em "ordem superior não trivial", quero dizer "usar instalações de ordem superior do formalismo computacional de maneira crítica na interface e / ou implementação do algoritmo"

jkff
fonte
3
Eu perguntei algo semelhante uma vez. Algumas respostas aqui: caml.inria.fr/pub/ml-archives/caml-list/2004/09/…
Radu GRIGore
Vocês estão falando sobre algoritmos que usam algoritmos e / ou retornam algoritmos?
Pratik Deoghare 01/09/10

Respostas:

13

Há muitas funções de ordem superior em http://math.andrej.com/ , por exemplo, na postagem sobre exponenciais duplas , o seguinte tipo de Haskell aparece (com os sinônimos de tipo expandidos):

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

Você também pode se divertir muito com a postagem A Haskell Monad for Infinite Search in Finite Time - por exemplo:

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

Eu acho que o tipo de bigUnion é de 4 ou 5 ordem!

yatima2975
fonte
22

existem vários algoritmos que são "realmente de segunda ordem", embora geralmente não sejam explicitamente descritos nesses termos. Sempre que temos algoritmos de tempo sub-lineares, implícito é algum tipo de acesso do oráculo à entrada, ou seja, realmente tratando a entrada como uma função.

Exemplos:

(1) Os algoritmos elipsóides ao trabalhar com um "oráculo de separação" (por exemplo, http://math.mit.edu/~vempala/18.433/L18.pdf )

(2) Minimização da função submodular (por exemplo, http://people.commerce.ubc.ca/faculty/mccormick/sfmchap8a.pdf )

(3) Todo o campo de teste de propriedades é realmente desse formato ( http://www.wisdom.weizmann.ac.il/~oded/test.html )

(4) Leilões combinatórios no modelo de consulta (por exemplo, http://pluto.huji.ac.il/~blumrosen/papers/iter.pdf )

Noam
fonte
15

Há outra resposta para essa pergunta: não há nenhuma. Mais especificamente, qualquer algoritmo de ordem superior (implementável!) É mecanicamente equivalente a um algoritmo de primeira ordem, usando a defuncionalização .

Deixe-me ser mais preciso: embora existam realmente algoritmos de ordem superior, na prática é sempre possível reescrever cada instância como um programa puramente de primeira ordem. Em outras palavras, não há programas saturados de ordem superior - essencialmente porque a entrada / saída dos programas são cadeias de bits. [Sim, essas cadeias de bits pode representar funções, mas esse é o ponto: eles representam funções, eles são não funções].

As respostas já dadas são excelentes, e minha resposta não deve ser considerada contraditória. Deve-se considerar como resposta à pergunta em um contexto um pouco maior (programas completos em vez de algoritmos independentes). E essa mudança de contexto muda a resposta radicalmente. O objetivo da minha resposta é lembrar às pessoas disso, que é fácil demais de esquecer.

Jacques Carette
fonte
Concordo que qualquer algoritmo de ordem superior é equivalente a algum algoritmo de primeira ordem com a mesma especificação externa, mas isso não deve nos impedir de discutir sobre suas propriedades internas. Não há diferença entre representar algo e ser algo.
Jkff 31/08/10
11
@jkff: Eu concordo com o seu primeiro ponto - nós definitivamente devemos discutir essas propriedades internas. Eu discordo enfaticamente do segundo ponto: você está de alguma forma afirmando que extensões e intensões são 'iguais', o que é apenas patentemente falso. [Lembra-me da pintura de Matisse 'isto não é um cachimbo']
Jacques Carette
Ah, sim, "A Traição da Conversão Eta". (\\() -> "Ceci n'est pas une fonction") ()
CA McCann
Eu estou dizendo que, se duas coisas são equivalentes (representando o outro), você não pode negar a existência de um deles :)
JKFF
@ jkff: difícil discordar disso!
Jacques Carette
13

Nas bibliotecas combinadoras do analisador, a ordem da função geralmente é bastante alta. Confira Funções de ordem superior para análise ou por que alguém iria querer usar uma função de sexta ordem? de Chris Okasaki. Journal of Functional Programming , 8 (2): 195-199, março de 1998.

Dave Clarke
fonte
Este é um ótimo artigo, mas não é exatamente o que estou procurando. Embora os combinadores sejam de ordem superior, eles são muito simples e independentes, e qualquer um deles dificilmente contaria como um algoritmo / estrutura de dados não trivial (no entanto, talvez os próprios analisadores de combinadores contassem). Pelo contrário, o combinador Y é um algoritmo altamente não trivial para encontrar um ponto fixo, e as listas de diferenças são uma estrutura de dados inteligente construída inteiramente a partir de funções de ordem superior. (Eu não estou minando a sua resposta, apenas a tentar esclarecer a minha pergunta)
JKFF
13

A análise computável caracteriza números reais programaticamente, uma vez que os números reais contêm uma quantidade ilimitada de informações e, portanto, as operações em números reais são de ordem superior no sentido das perguntas. Normalmente, os números reais são apresentados usando uma visão topológica no fluxo infinito de bits, o espaço Cantor, emprestando interesse ao campo mais amplo da topologia computável.

Klaus Weihrach falou disso como a Hierarquia de Efetividade do Tipo Dois da topologia computável. Para mais informações, consulte Weihrach & Grubba, 2009, Topologia computável elementar e a página de pesquisa de John Tucker, Computação com dados topológicos . Menciono a página de Tucker na minha pergunta, Applications of Cantor Space .

Charles Stewart
fonte
E isso se estende naturalmente aos objetos matemáticos computáveis ​​em geral: outros números computáveis ​​(não necessariamente reais), elementos computáveis ​​de grupos infinitos (anéis, álgebras, ...), pontos computáveis ​​nos espaços, etc. Em todos esses casos, o algoritmo A teoria diz respeito à extração de informações da representação funcional (de como calcular o objeto matemático), e não do próprio objeto.
ex0du5
13

Um módulo de continuidade funcional é um mapa mque aceita uma (contínua) funcional F : (nat -> nat) -> nate gera um número ktal que F f = F gsempre f i = g ipara todos i < k. Existem algoritmos para calcular o módulo de continuidade (não muito eficientes), o que o torna uma instância de um algoritmo de terceira ordem.

Andrej Bauer
fonte
9

Para complementar a resposta de Noam , também existem várias situações em que é importante que a saída seja (uma representação explícita de) uma função.

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

AgA2/3ϵmmα

arnab
fonte
5

Nos algoritmos de gráfico, os vértices e as arestas são geralmente considerados dados simples, mas na verdade podem ser generalizados de maneira produtiva para que sejam gerados programaticamente sob demanda.

Durante meu doutorado (em química computacional), implementei muitos algoritmos de gráficos em forma de ordem superior, a fim de aplicá-los à análise de gráficos implícitos, principalmente porque meus gráficos reais eram infinitos, então eu não podia armazená-los explicitamente! Especificamente, eu estava estudando a topologia de materiais amorfos representados como inclinações 3D de células unitárias (supercélulas).

Por exemplo, você pode escrever uma função para calcular o shell vizinho enésimo mais próximo de um vértice de origem 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))

onde neighborsé uma função que retorna o conjunto de vértices vizinhos ao vértice fornecido.

Por exemplo, a estrutura quadrada 2D:

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

Outros algoritmos interessantes nesse contexto incluem as estatísticas de anel de caminho mais curto de Franzblau.

Jon Harrop
fonte
Isso me leva a uma pergunta que fiz uma vez. Se existem maneiras programáticas de definir gráficos dessa maneira, existe uma maneira de definir um gráfico paradoxal auto-referencial?
precisa
11
{x:xx}{x:xx}
Certo. Mas isso é um gráfico auto-referencial ?
Suresh Venkat
@ Suresh: é um gráfico definido em uma linguagem funcional no sentido de que existe um tipo Ude vértices e uma função U -> U -> Boolde arestas.
Sdcvvc 29/07