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

Question

Я задал аналогичный вопрос на cstheory.se.

Согласно с этот ответ на Stackoverflow Существует алгоритм, который на не-ленивом чистом языке функционального программирования имеет сложность $ omega (n log n) $, в то время как тот же алгоритм в императивном программировании-$ omega (n) $. Добавление ленивого языка FP сделает алгоритм $ omega (n) $.

Есть ли какие -либо эквивалентные отношения, сравнивая язык FP с функциями более высокого порядка и без него? Это все еще заполнено? Если это так, делает ли отсутствие более высокого порядка на FP языком менее «мощным» или эффективным?

Answer 1

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

Однако, если язык недостаточно силен, то да, более высокий порядок обеспечивает выразительную силу. Рассмотрим Lambda-Calculus: без какой-либо функции более высокого порядка он действительно ничего не может сделать, в основном потому, что самые основные типы данных (целые числа, логические) реализованы с использованием функций.

В заключение, это действительно зависит от языка.

---

Выше мой ответ. Ниже комментарий о обычном предположении об императивных языках.

Об алгоритме, который на нездоровом языке функционального программирования имеет сложность $ omega (n log n) $, в то время как тот же алгоритм в императивном программировании-$ omega (n) $. Добавление ленивого языка FP сделает алгоритм $ omega (n) $.

Я хотел бы увидеть эту ссылку. Обычное предположение состоит в том, что доступ к массиву длины $ n n $ в оперативной памяти со временем $ O (1) $, а эквивалент в Pure FP вовремя $ O ( log n) $. Это не совсем так: время доступа в ОЗУ находится в $ O ( log M) $, где $ M $ - это размер памяти. Конечно, $ m≥n $. На практике доступ к элементу массива намного быстрее. Причиной будет то, что $ m $ ограничена, но ... так же $ n $!

РЕДАКТИРОВАТЬ: Спасибо за ссылку (ссылка на газету о лени недоступна, Вот еще один) Как опубликовано в комментариях и выше в моем ответе, модель ОЗУ немного несправедливой по отношению к чистому FP, предоставляя $ O (1) $-время поиска времени, даже если размер одного адреса не ограничен. Я еще не понял, как работает ленивый трюк, но я думаю, что важно отметить, что это только для этой конкретной проблемы.

Answer 2

Это зависит от того, что вы имеете в виду под выразительностью.

Вот аргумент, что высший заказ что-то добавляет: с языками первого порядка примитивная рекурсия недостаточно, чтобы выразить Функция Ackermann. Анкет Однако в присутствии функций высшего порядка достаточно примитивной рекурсии:

$$ begin {array} {lcl} textIt {ackermann} 0 & = & lambda x. x+1 textit {ackermann} (m+1) & = & textit {iter} ( textit {ackermann} m) textit {iter} f 0 & = & f 1 Textit {iter} f (n+1) & = & f ( textit {iter} f n) end {array} $$

Это определяет функцию Ackermann с использованием только примитивной рекурсии.

Обратите внимание, что $ textit {iter} $ не определяется в обычной теории рекурсии, потому что $ textit {iter} $ является более высоким порядком. В традиционной теории рекурсии все определяемые функции имеют тип $ mathbb {n}^k rightarrow mathbb {n} $ для некоторого $ k $, в то время как $ textit {iter} $ имеет тип $ ( mathbb {n} rightArrow mathbb {n}) rightarrow ( mathbb {n} rightarrow mathbb {n}) $.