Алгоритмы высшего порядка

35

Большинство известных алгоритмов первого порядка в том смысле, что их ввод и вывод являются «простыми» данными. Некоторые из них являются вторым порядком тривиальным способом, например, сортировка, хеш-таблицы или функции map и fold: они параметризуются функцией, но на самом деле они не делают с ней ничего интересного, кроме как вызывают ее для фрагментов других входных данных.

Некоторые из них также второго порядка, но несколько интереснее:

  • Пальцы, параметризованные моноидами
  • Расщепление дерева пальцев на однообразный предикат
  • Алгоритмы суммирования префиксов, опять же обычно параметризованные моноидом или предикатом и т. Д.

Наконец, некоторые из них «действительно» более высокого порядка в том смысле, который мне наиболее интересен:

  • Y комбинатор
  • Списки различий

Существуют ли другие нетривиальные алгоритмы высшего порядка?

В попытке прояснить мой вопрос, под «нетривиальным высшим порядком» я подразумеваю «использование средств вычислительного формализма более высокого порядка критически в интерфейсе и / или реализации алгоритма»

jkff
источник
3
Я однажды спросил что-то подобное. Несколько ответов здесь: caml.inria.fr/pub/ml-archives/caml-list/2004/09/…
Radu GRIGore
Ребята, вы говорите об алгоритмах, которые используют алгоритмы и / или возвращают алгоритмы?
Pratik Deoghare

Ответы:

13

На http://math.andrej.com/ есть много функций высшего порядка , например, в посте о двойных экспонентах появляется следующий тип языка Haskell (с расширенными синонимами типа):

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

Вы также можете получить массу удовольствия от поста «Монада Хаскелла для бесконечного поиска за конечное время», например:

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

Я думаю, что тип bigUnion 4-го или 5-го порядка!

yatima2975
источник
22

Есть множество алгоритмов, которые «действительно 2-го порядка», хотя обычно не описаны явно в этих терминах. Всякий раз, когда у нас есть сублинейные алгоритмы времени, неявный - это своего рода доступ к входу оракула, то есть действительно обработка входа как функции.

Примеры:

(1) Алгоритмы эллипсоидов при работе с «оракулом разделения» (например, http://math.mit.edu/~vempala/18.433/L18.pdf )

(2) Минимизация субмодулярных функций (например, http://people.commerce.ubc.ca/faculty/mccormick/sfmchap8a.pdf )

(3) Вся область тестирования свойств действительно имеет такую ​​форму ( http://www.wisdom.weizmann.ac.il/~oded/test.html )

(4) Комбинаторные аукционы в модели запросов (например, http://pluto.huji.ac.il/~blumrosen/papers/iter.pdf )

Ноам
источник
15

На этот вопрос есть другой ответ: их нет. Более конкретно, любой такой (реализуемый!) Алгоритм более высокого порядка механически эквивалентен алгоритму первого порядка с использованием дефункционализации .

Позвольте мне быть более точным: хотя действительно существуют алгоритмы высшего порядка, на практике всегда можно переписать каждый экземпляр как программу первого порядка. Другими словами, не существует насыщенных программ высшего порядка - в основном потому, что ввод / вывод программ - это битовые строки. [Да, эти битовые строки могут представлять функции, но в том-то и дело: они представляют функции, они не являются функциями].

Ответы, которые уже даны, превосходны, и мой ответ не должен рассматриваться как противоречащий им. Это следует рассматривать как ответ на вопрос из более широкого контекста (полные программы вместо автономных алгоритмов). И это изменение контекста меняет ответ довольно радикально. Суть моего ответа - напомнить людям об этом, что слишком легко забыть.

Жак Каретт
источник
Я согласен, что любой алгоритм более высокого порядка эквивалентен некоторому алгоритму первого порядка с той же внешней спецификацией, но это не должно мешать нам спорить об их внутренних свойствах. Нет никакой разницы между тем, чтобы представлять что-то и быть чем-то.
jkff
1
@jkff: Я согласен с вашим первым замечанием - нам определенно следует обсудить эти внутренние свойства. Я категорически не согласен со вторым пунктом: вы как-то утверждаете, что расширения и намерения «одинаковы», что является явно ложным. [Напоминает мне картину Матисса «это не труба»]
Жак Каретт
Ах, да, «Предательство конверсии эта». (\\() -> "Ceci n'est pas une fonction") ()
CA McCann
Я утверждаю, что если две вещи эквивалентны (представляя друг друга), вы не можете отрицать существование одной из них :)
jkff
@jkff: трудно с этим не согласиться!
Жак Каретт
13

В библиотеках комбинатора синтаксического анализа порядок функции обычно довольно высок. Проверьте даже функции высшего порядка для разбора или почему кто-то когда-либо хотел использовать функцию шестого порядка? Крис Окасаки. Журнал функционального программирования , 8 (2): 195-199, март 1998.

Дэйв Кларк
источник
Это отличная статья, но не совсем то, что я ищу. Хотя комбинаторы более высокого порядка, они очень просты и независимы, и любой из них вряд ли будет считаться нетривиальным алгоритмом / структурой данных (однако, возможно, сами парсеры комбинатора будут). Напротив, Y-комбинатор является весьма нетривиальным алгоритмом для нахождения фиксированной точки, а списки различий - это умная структура данных, построенная полностью из функций более высокого порядка. (Я не подрываю ваш ответ, просто пытаюсь уточнить мой вопрос)
jkff
13

Вычислительный анализ программно характеризует действительные числа, так как действительные числа содержат неограниченный объем информации, и поэтому операции с действительными числами имеют более высокий порядок в смысле вопросов. Как правило, действительные числа представляются с использованием топологического представления о бесконечном потоке битов, пространстве Кантора, что представляет интерес для более широкого поля вычислимой топологии.

Клаус Вейрах говорил об этом как о иерархии второго типа эффективности вычислимой топологии. Подробнее об этом см. В Weihrach & Grubba, 2009, Elementary Computable Topology , и на исследовательской странице Джона Такера « Вычисления с топологическими данными» . Я упоминаю страницу Такера в моем вопросе, Применения Пространства Кантора .

Чарльз Стюарт
источник
И это вполне естественно распространяется на вычислимые математические объекты в целом: другие вычислимые числа (не обязательно действительные), вычислимые элементы бесконечных групп (кольца, алгебры, ...), вычислимые точки в пространствах и т. Д. Во всех таких случаях алгоритмический Теория касается извлечения информации из функционального представления (о том, как вычислять математический объект), а не из самого объекта.
ex0du5
13

Модуль непрерывности функционала представляет собой карту , mкоторая принимает (непрерывный) функциональна F : (nat -> nat) -> natи выводит число kтаких , что F f = F gвсякий раз , когда f i = g iдля всех i < k. Существуют алгоритмы для вычисления модуля непрерывности (не очень эффективные), что делает его экземпляром алгоритма 3-го порядка.

Андрей Бауэр
источник
9

Чтобы дополнить ответ Ноама , есть также несколько ситуаций, когда важно, чтобы выходные данные были (явным представлением) функции.

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

Ag denotes the fraction of coordinates that the two strings agree on. In other words, for every received word, the output of A must contain, with probability at least 2/3, a machine that ϵ-approximates m for every message m whose encoding agrees with at least α fraction of the coordinates of the received word.

arnab
источник
5

In graph algorithms, vertices and edges are usually thought of as being plain data but they can actually be productively generalized so that they are programmatically generated on-demand.

During my PhD (in computational chemistry) I implemented many graph algorithms in higher-order form in order to apply them to the analysis of implicit graphs, mainly because my actual graphs were infinite so I could not afford to store them explicitly! Specifically, I was studying the topology of amorphous materials represented as 3D tilings of unit cells (supercells).

For example, you can write a function to compute the nth-nearest neighbor shell of an origin vertex i like this:

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

where neighbors is a function that returns the set of neighboring vertices to the given vertex.

For example, the 2D square lattice:

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

Other interesting algorithms in this context include Franzblau's shortest path ring statistics.

Jon Harrop
источник
This brings me to a question I had once. If there are programmatic ways of defining graphs this way, is there a way to define a self-referential paradoxical graph ?
Suresh Venkat
1
@Suresh: it is possible to replicate Russell's paradox in a functional language; evaluating {x:xx}{x:xx} will get stuck in an infinite loop. See, for example, blog.sigfpe.com/2008/01/type-that-should-not-be.html
sdcvvc
Конечно. Но это самореферентный граф ?
Суреш Венкат
@Suresh: It is a graph defined in a functional language in the sense that there is a type U of vertices and a function U -> U -> Bool of edges.
sdcvvc